|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...
Here is my solution.
- 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.
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)
solve more problems and distil concepts