## 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**

## Top comments (0)