Question List

• Loading...
• Fetching Title#c2ia
• Loading...
• Dynamic Programming Patterns - LeetCode Discuss

One thing that helped me was coming up with a recursive solution to the problem, then take a look at the parameters you are passing to the recursive function. Then check which parameters change between calls, those are likely the coordinate in your dp array/matrix.

Understand how the recursive call generates its answer from the sub recursive calls, try to put that into an equation, like currentRes = f(subRes). That would be your DP build up equation.

Lastly find the exit case of the recursive function, that is the base case that you need to built up from in DP.

Hope this helps.

Note

• When doing DP question, alway consider the different cases of the sub problem
• Three key component for each DP problem
  • the function or array with parameters
  • Recurrence relation
  • base cases

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

Question types

1D DP

• Optimising method

  • Recursion
  • memo - top down
  • DP - bottom up
  • DP using constant space complexity

• Alway attempt to find the subproblem first

  • Find the easiest sub problem to solve, which is usually the beginning or the end
  • Sub problem is usually subset of [0, 1]

• 91. Decode Ways

• 639. Decode Ways II

• 264. Ugly Number II

• 32. Longest Valid Parentheses

• 940. Distinct Subsequences II

• 276. Paint Fence
  1395. Count Number of Teams
  1014. Best Sightseeing Pair

Longest Increasing Subsequence

• 646. Maximum Length of Pair Chain

2D DP

• Optimising method

  • Recursion
  • memo - top down
  • DP - bottom up
  • DP using constant space complexity - Can reduce from n^2 to n if processing line by line

• Question with complex variable are usually not DP (such as row and col, which are both simple integers)

  • 79. Word Search

• Interval 2D DP

• 1143. Longest Common Subsequence

• 115. Distinct Subsequences

Knapsack questions

Interval DP

877. Stone Game

1062. Longest Repeating Substring