Non-CS person explains Dynamic Programming (DP)

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.

• Neetcode Problem List
• Memoization VS Tabulation
• Memoization (1D, 2D, and 3D)

If I had to count the number of times I solved Fibonacci...

EXAMPLE 1: Climbing Stairs (Leetcode: Easy)

Here is my solution.

IDEA

1. Recursion is intuitive but will TLE.
2. Memoization reduces runtime complexity but might Stack Overflow.
3. 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