DEV Community

ZhiHong Chua
ZhiHong Chua

Posted on • Updated on

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.

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)
Enter fullscreen mode Exit fullscreen mode

TODO

solve more problems and distil concepts

Top comments (0)