Week8 algorithm practice(DP)
[SUMMARY]
Step one: Write down the relational equation. For example:
F[i] = max/min ( F[i-num], F[i])
Step two: Try to save space, ex: 2D->1D
Step tree: Be careful for boundary problems
[120. Triangle][medium]
Find the minimum path from top of triangle to down of triangle
Core Idea: F(i,j) = min (f(i+1,j), f(i+1,j+1))
Method I: recursive to find the next lawyer, and record each f(i,j) whenever it is figured out to avoid time exceeded. [more easy to understand]
Method II: Iterative calculate the lawyer from down to top. This method will be more efficient. And the space complexity is O(one lawyer of triangle)
[64. Minimum Path Sum][medium]
Given a grid, and find the min path from top left to down right.
This is a classical DP problem. First step is to write down to relative function.
F(i,j) = min(f(i-1,j),f(i,j-1)) + grid[i][j]
Time complexity : O(m*n)
Space complexity: O(m*n)
[ 213. House Robber II][medium]
Can’t choose two elements adjacent to each other. And the first one is viewed as adjacent to last one.
Method: Two times of DP, choose first one and does not choose first one
[ 279. Perfect Squares][medium]
Given a positive integer n, find the least number of perfect square numbers.
Method I: 2-dimensional DP
MethodII: 1-dimensional DP
MethodIII: efficient 1D DP
Core idea: DP[i] = min(DP[i], DP[i-num]+1)
Time complexity of both Method I and Method II should be the same:
O(m*n), m is the max square number smaller than n
However, space complexity should be a little bit different
Space complexity of method I : O(n)
Space complexity of method I : O(mn)
