Week8 algorithm practice(DP)

[SUMMARY]

I-Hsien Huang
Sep 6, 2018 · 2 min read

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)

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade