Summary
| Method | Pro | Con | Time Complexity | Space Complexity |
|---|---|---|---|---|
| 1. Recursion | Intuitive | May Exceed Time Limit | O(d^N), where d = number of choice at each recursion step | O(1) |
| 2. Memoization (Top-Down) | Intuitive, Saves Time | May Stack Overflow | O(N), all repeat function calls are retrieved from memo/dp table | O(N) |
| 3. Tabulation (Bottom-Up) | Saves Time | Non-Intuitive | O(N) | O(1) to O(N) |
Here's hoping this post will document learnings to help you guys consistently solve DP Hard problems.
If I had to count the number of times I solved Fibonacci...
EXAMPLE 1: Climbing Stairs (Leetcode: Easy)
Here is my solution.
IDEA
- Recursion is intuitive but will TLE.
- Memoization reduces runtime complexity but might Stack Overflow.
- Tabulation reduces runtime complexity but it's hard to figure out the iteration formula.
EXAMPLE 2: Out of Boundary Paths (Leetcode: Medium)
3D-memoization works here. No need to go extreme mode into Tabulation.
dp = [[[-1] * (maxMove + 1) for _ in range(n+1)] for _ in range(m+1)]
def dfs(r,c,k):
if k < 0:
return 0
if r < 0 or c < 0 or r == m or c == n:
return 1
if dp[r][c][k] != -1:
return dp[r][c][k]
dp[r][c][k] = dfs(r-1,c,k-1) + dfs(r+1,c,k-1) + dfs(r,c-1,k-1) + dfs(r,c+1,k-1)
return dp[r][c][k]
return dfs(startRow, startColumn, maxMove) % (10 ** 9 + 7)
TODO
solve more problems and distil concepts
Latest comments (0)