Dynamic Programming

Notes and typical questions for dynamic programming algorithm

Notes

Steps to resolve the problem
1. Define the meaning of the DP array (dp table) and its indices
2. Determine the recurrence formula
3. Initialize the DP array
4. Define the traversal order
5. Use an example to derive the DP array

Typical Questions

Miscellaneous DP

LC 509. Fibonacci Number
LC 1137. N-th Tribonacci Number
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$
LC 118. Pascal's Triangle
- Optimal Answer. TC: $O(numRows^2)$ , SC: $O(1)$ (without considering space for storing the result)
LC 70. Climbing Stairs
LC 746. Min Cost Climbing Stairs
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$
🔴 LC 790. Domino and Tromino Tiling
- TBH, it's very hard. I will forget how to solve it next time.
- Answer. This answer is not optimal, but more readable. TC: $O(n)$ , SC: $O(n)$

LC 343. Integer Break

🟠 Method 1: DP
- Answer. TC: $O(n^2)$ , SC: $O(n)$
🔴 Method 2: Math

// 把一个正整数拆成若干个正整数，使其拆分后的数乘积最大，
// 假设 N = n1 + n2 + ... + nk;

// 1. 显然，1 不在n1...nk中
// 2. 如果对于某 i 有 ni >= 5, 那么把 ni 拆成 3+(ni-3), 我们有3(ni-3) = 3ni -9 > ni, 所以不存在>=5的因子
// 3. 如果 ni = 4, 拆成 2+2, 乘积不变，所以不妨假设没有4
// 4. 如果拆成三个以上的2，那么 3*3 > 2*2*2，所有替换成3乘积最大, 不可能有>=3个2
// 综上，选用尽量多的3，直到剩下2或者4时用2.

if (n == 2) return 1;
if (n == 3) return 2;
int num_3 = (int)n/3;
int remainder = n % 3;
if (remainder == 1) {
    remainder = 4;
    num_3 --;
} else if (remainder == 0) 
    remainder = 1;

return (int)Math.pow(3, num_3) * remainder;

⚪ LC 96. Unique Binary Search Trees
- DP Answer. TC: $O(n^2)$ , SC: $O(n)$
🔴 LC 312. Burst Balloons
- It's super hard to come up with the correct idea
- Optimal Solution. TC: $O(n^3)$ , SC: $O(n^2)$
🔴 LC 3351. Sum of Good Subsequences
- Use both longand module operation to avoid overflow.
- Optimal Answer. TC: $O(n)$ , SC: $O(n)$
🔴 LC 2184. Number of Ways to Build Sturdy Brick Wall
- It's very complicated: DP + Backtracking + Bit
- Optimal Answer.
  - Assume $B$ is the number of brick sizes, $H$ and $W$ are the height and width of the wall, $N$ is the number of ways to build 1 row
  - TC: $B^{W}+H*N^{2}$
  - SC: $N^{2}+H*H$
🔴 LC 3287. Find the Maximum Sequence Value of Array
- Optimal Answer. TC: $O(n*k)$ , SC: $O(n*k)$
🟠 LC 2327. Number of People Aware of a Secret
- I came up with an n^2 solution, but that's not good enough.
- The definition of this dp array and how to do state transition is tricky.
- Optimal Answer. TC: $O(n)$ , SC: $O(n)$

Pattern Counting

Notes
- Group configurations into a few pattern types instead of enumerating all possibilities.
- Let each pattern type be a DP state representing how many ways it can appear.
🟠 LC 1411. Number of Ways to Paint N × 3 Grid
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$

2D Matrix Problems

LC 62. Unique Paths
- Optimal Answer. TC: $O(m*n)$ , SC: $O(n)$
LC 63. Unique Paths II
- Optimal Answer. TC: $O(m*n)$ , SC: $O(1)$ . This approach modifies input data so it's. kind of hacky.
- Answer. TC: $O(m*n)$ , SC: $O(n)$ .
LC 221. Maximal Square
- Optimal Solution. TC: $O(m*n)$ , SC: $O(1)$
🔴 LC 2713. Maximum Strictly Increasing Cells in a Matrix
- It's very hard to come up with this solution.
- For each point, a separate data structure must be used to help find the current max step in its column and row.
  - Optimal Solution. TC: $O(n*m*log{nm})$ , SC: $O(n*m)$
LC 120. Triangle
- Optimal Answer. TC: $O(n^2)$ , SC: $O(n)$
LC 64. Minimum Path Sum
- Optimal Answer. TC: $O(m*n)$ , SC: $O(n)$
🔴 LC 808. Soup Servings
- This DP problem requires some techniques I never seen before.
- Core Idea
  - How to address stack overflow or TLE if using backtracking?
    Use DP
  - What's the base case of DP?
  - How to address Memory Limit Exceeded when the DP table is too big?
    Based on the law of large numbers, we don't have to calculate every case when the input is too big because the problem mentions that answers within 1e-5 are accepted.
  - What's the traversal order if we may not want to calculate every case
    Not line by line or column by column. We should go from (i, i) to (i+1,i+1)
- Optimal Answer. TC: $O(1)$ , SC: $O(1)$

Knapsack Problems

🧩 0-1 Knapsack Problem

Notes
- Assumption: Each item can only be used once to fill a knapsack of size k.
- Kinds of problems
  - The maximum value to fill the knapsack <-> Whether it is possible to fill a knapsack of size k
  - The number of ways to fill a knapsack of size k (be careful about initialization)
  - The max/min number of items to fill the knapsack of size k
🌟 🔴 LG P1048 [NOIP2005 普及组] 采药
- Be careful when using 1D array: inner loop iteration order & size of 1D array & inner loop termination logic
LC 416. Partition Equal Subset Sum
- Optimal Answer. TC: $O(n*target)$ , SC: $O(target)$
LC 1049. Last Stone Weight II
- Optimal Answer. TC: $O(n*target)$ , SC: $O(target)$
  为什么两两单个相撞可以等效于两个group相撞：整个题目，每个回合数两两抽出来比较，两个数之差将被再一次扔到数组里面，继续上面的过程。每个回合都会丢失掉两个数字，加入一个新的数字，这个数字就是两个数的差。相当于来说，就是少了a和b，但是多了一个a-b，a,b就此消失，但是在下一回合，a-b可能又被抓出去pk，pk后a-b就此再消失了，又产生了新的一个差。那么每一步来说，其实就相当于a,b没有真正意义消失。到了最后一回合，我们可以知道，其实找出两个最接近的数字堆。再举个例子：【31,26,33,21,40】 1:40-21 【19,26,31,33】 2: 31-(40-21) 【12,26,33】 3: 33-(31-(40-21)) 【21,26】 4: 26-(33-(31-(40-21))) 【5】总：（26+31+21） - （40+33）这就是找出两个总和接近的两个堆。如何让两个堆接近呢？那就是沿着中间分两半，找左右各自那一半，那么思路就来到了找出一半堆这里。那么就自然而然地来到取不取的问题，就是01背包问题。
🔴 LC 494. Target Sum
- Optimal Answer. TC: $O(n*part1)$ , SC: $O(part1)$
🟠 LC 474. Ones and Zeroes
- Optimal Answer. TC: $O(l*m*n)$ , SC: $O(m*n)$
🌟 🔴 1235. Maximum Profit in Job Scheduling
- I came up with the main idea by myself, but my original answer failed due to "Memory Limit Exceeded". The gap is that I did not find a way to compress the DP array from (0, maxEndTime) to (0, number of unique jobEndTimes).
- Both answers below are optimal. TC: $O(n*logn)$ , SC: $O(n)$
  - DP + TreeMap Answer.
  - DP + Binary Search Answer. While it has the same TC as the TreeMap answer, it is faster based on the LC evaluation.

🧩 Complete Knapsack Problem

Notes
- Assumption: Each item can only be used multiple times to fill a knapsack of size k.
- Kinds of problems
  - The maximum value to fill the knapsack
  - The number of ways to fill a knapsack of size k (be careful about initialization)
  - The max/min number of items to fill the knapsack of size k
- The ORDER of the INNER and OUTER loop
  - High level speaking, 对于纯粹的完全背包，是否能调换两层循环（物品，重量）？从结果角度，可以。从过程角度，如果先循环重量，再循环物品，中间有些dp[i]的含义会有问题，会超前使用某些之前的值做推断，但不影响结果。可用 w: (1,2,3,4), v: (10, 21, 33, 44),分别写两种方法的dp表格。对于完全背包的相关应用，内外循环不一定能调换。
  - Low-level speaking
    Outer loop for items & inner loop for weights -> get the result from all combinations
    Outer loop for weights & inner loop for items -> get the result from all permutations
🌟 🔴 LG P1616 疯狂的采药
LC 518. Coin Change II
- Looks like a backtracking problem but it's easier to solve it using DP.
- Optimal Answer. TC: $O(n*amount)$ , SC: $O(amount)$
- This is a combination problem. Its iteration must be "outer loop for items & inner loop for weights". If you do it in reverse way, you will get a permutation result.
  对于外层遍历物品的时候，对于每一个物品比如物品1，内层是在不断地遍历背包容量，这个物品可以被重复地添加进来，当外层遍历到下一个物品2的时候，内层又会不断地遍历背包容量，这个物品也可以被重复地添加进来，但是这个物品2一定是在物品1后面的，不会出现物品2 物品1这种情况，所以是没有考虑到物品的顺序的，所以是组合如果外层遍历背包，内层物品，那么对于每一个背包容量，都会把所有物品遍历一次，虽然在本次外层循环中，物品2会在物品1之后，但是下一个外层循环的时候，又会遍历所有物品，整体看起来就会出现物品1 物品2 物品1这种情况了，所以是排列问题。
LC 377. Combination Sum IV
- It's actually a permutation problem...It's very similar to LC 518. Coin Change II and the only difference is its requirement on the order of the result.
- 70. Climbing Stairs problem can be abstracted to this problem as well. However, compared to thinking about it in a complete knapsack way, the original idea is better.
- Optimal Answer. TC: $O(n*target)$ , SC: $O(target)$
🌟 ⚪ LC 322. Coin Change
- Optimal Answer. TC: $O(n*amount)$ , SC: $O(amount)$
LC 279. Perfect Squares
- It's the same as the above one.
- Optimal Answer. TC: $O(n*\sqrt{n})$ , SC: $O(n)$
🟠 LC 139. Word Break
- This question is also put in the Trie section.
- Given $n$ as the length of s, $m$ as the length of wordDict, and $k$ as the average length of the words in wordDict
  - Straightforward DP Answer.
    TC: $O(n^3 + m*k)$
    SC: $O(n+m*k)$
  - 👍 Optimal Answer (DP+Trie).
    The idea of doing dp is different from the above straightforward one.
    TC: $O(n^2+m*k)$
    SC: $O(n+m*k)$
  - 👍 Knapsack Answer.
    TC: $O(n*m*k)$
    SC: $O(n)$

House Robber

🌟 LC 198. House Robber
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$
🌟 ⚪ LC 213. House Robber II
- Transform a circular problem into a linear one using case-by-case analysis. (case1: exclude 1st item, case2: exclude last item)
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$
🟠 LC 337. House Robber III
- Tree DP. I have most of the main idea, but it's easy to make mistakes in the case where the current node is not being robbed.
- Optimal Answer. TC: $O(n)$ , SC: $O(h)$
⚪ LC 3186. Maximum Total Damage With Spell Casting
- House Robber Variant: conflict defined by value distance instead of index adjacency. Need to find the last compatible state.
- TC: $O(nlogn)$ , SC: $O(n)$

🧩 Stock Problems

Notes
- General assumptions
  - You can only hold at most 1 share of stock at any time
  - Must sell the stock before you buy again
  - Transaction times k (most important assumption)
    if no requirement on k, then 2 states for stocks (hold or not hold)
    if k == i (i is an input constant), then 2*k state for stocks
    For example, if k == 2, states: s0 -> 1st hold, s1 -> 1st not hold, s2 -> 2nd hold, s3 -> 2nd not hold
  - Have a cooldown day or not (easy to add this logic)
  - Have transaction fee or not (easy to add this logic)
- Key: Define stock holding status, usually defined as dp[i][s], i -> ith day, s -> all states based on assumption
🌟 🟠 LC 121. Best Time to Buy and Sell Stock
- Alternative greedy algo answer: For each prices[i], find the min value which is on the left (including the current one), and keep updating result.
- DP answer can be improved to a 1D DP array.
- Approach 1 with DP: Optimal Answer. TC: $O(n)$ , SC: $O(1)$
- Approach 2 with brute force: Optimal Answer. TC: $O(n)$ , SC: $O(1)$
LC 122. Best Time to Buy and Sell Stock II
- Alternative greedy algo answer: Accumulate positive revenue and keep updating results.
- DP answer can be improved to a 1D DP array with tmp var.
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$
  - 也可以不用tmp, 相当于允许当天买入+卖出的操作。
🌟 🟠 LC 123. Best Time to Buy and Sell Stock III
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$
- 也可以把for循环里面的顺序正过来，原因如下
- 大家会发现dp[1]利用的是当天的dp[0]。但结果也是对的。
  我来简单解释一下：
  dp[0] = max(dp[0], -prices[i]);
  如果dp[0] 取 dp[0]，即保持买入股票的状态，那么 dp[1] = max(dp[1], dp[0] + prices[i]); 中 dp[0] + prices[i] 就是今天卖出。
  如果dp[0] 取 -prices[i]，今天买入股票，那么 dp[1] = max(dp[1], dp[0] + prices[i]); 中 dp[1] + prices[i] 相当于是今天再卖出股票，一买一卖收益为0，对所得现金没有影响。相当于今天买入股票又卖出股票，等于没有操作，保持昨天卖出股票的状态了。
LC 188. Best Time to Buy and Sell Stock IV
- Similar to LC 123
- Optimal Answer. TC: $O(n*k)$ , SC: $O(k)$
🟠 LC 309. Best Time to Buy and Sell Stock with Cooldown
- Approach 1 with 2 states: Answer. TC: $O(n)$ , SC: $O(n)$ . Not easy to compress its SC.
- 👍 Approach 2 with 3 states: Optimal Answer. TC: $O(n)$ , SC: $O(1)$
LC 714. Best Time to Buy and Sell Stock with Transaction Fee
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$ .

Subsequence/Subarray Problems

Notes
- Difference
  - subsequence: order matters, can skip element
  - substring: order matters, must consecutive
- For subsequence problems, think about "If I pick an element, what info about the past do I need to know to decide if I can append it?"
  - That info becomes your DP state.
    If it’s just the last value → dp[last]
    If it’s last two-ish pattern → dp[a][b] (like LC3202)
    If it’s last value + budget → dp[last][used]
    The “budget” can be anything constrained:
    number of changes
    number of mismatches
    number of deletions
    number of replacements
    number of violations
    number of operations

🧩 Classic Subsequence/Subarray

🌟 LC 300. Longest Increasing Subsequence
- Approach 1: Classic DP
  - dp[i]: longest increasing subsequence including nums[i]
  - Answer. TC: $O(n^2)$ , SC: $O(n)$
- 👍 🔴 Approach 2: Intelligently Build a Subsequence + Binary Search
  - This approach is hard to understand. I feel like its core logic/concept (keep exploring the array though elements within the array are not always valid) is similar to another 2-pointer question.
  - While the content of sub might not be an actual subsequence from nums, its length corresponds to the length of the LIS. This is because every time we append a number to sub, it means we have found a longer increasing sequence than any we have seen before. When we replace an element in sub, we're not extending the length of the sequence, but we are making the increasing sequence that we can potentially build later more flexible (i.e., able to accommodate smaller subsequent numbers).
  - Optimal Answer. TC: $O(n*log{n})$ , SC: $O(n)$
- 🔴 Approach 3: Segment Tree
  - Answer. Let n be the input length, and m be max-min+1
  - TC: $O(nlogm)$
  - SC: $O(m)$
🔴 LC 354. Russian Doll Envelopes
- It's not a DP question but I add it here because it relates to above LC 300.
- Key points
  - It's actually a 2D version of LIS (LC 300). We can sort 1st dimension and do LIS on 2nd dimension.
  - For sorting, you need a clever trick to solve some edge cases (when 1st dimensions of different elements are equal)
- Optimal Answer. TC: $O(n*log{n})$ , SC: $O(n)$
🌟 LC 674. Longest Continuous Increasing Subsequence
- Similar to LC 300
- Optimal Answer. TC: $O(n)$ , SC: $O(1)$
🌟 ⚪ LC 718. Maximum Length of Repeated Subarray
- dp[i][j]: max length of repeated subarray including nums1[i-1] and nums2[j-1]. Use i-1 and j-1 because it's easy to implement it without doing extra initialization.
- It's easy to make mistakes when you want to compress it to a 1D dp array.
- Optimal Answer. TC: $O(m*n)$ , SC: $O(n)$
🌟 ⚪ LC 1143. Longest Common Subsequence
- dp[i][j]: max length of common subsequence between nums1[0:i-1] and nums2[0:j-1]. It does NOT require that common sequence must include nums1[i-1] and nums2[j-1] like LC 718 and LC 674
  求递增序列的时候，因为要求序列有序，所以必须确定序列最后一个元素的值，才能比较新加入序列的元素是不是递增的。求相等序列的时候，如果求连续相等子序列，则还是要确定序列最后一个元素的值；但是本题求的是不必连续的相等子序列，就不需要知道序列最后一个元素的值，只要知道范围内相等的序列长度就行，新来的相等元素可以直接加在序列后面
- Optimal Answer. TC: $O(M*N)$ , SC: $O(min(M,N))$
  - Compressing space needs a special technique.
LC 1035. Uncrossed Lines
- Same as above LC 1143
- Optimal Answer. TC: $O(M*N)$ , SC: $O(min(M,N))$
🟠 LC 3202. Find the Maximum Length of Valid Subsequence II
- Optimal Answer. TC: $O(n*k)$ , SC: $O(k^2)$
🟠 LC 898. Bitwise ORs of Subarrays
- This problem isn’t about computing every subarray OR (which leads to $O(n^2)$ ), but about realizing that for each ending index, the number of distinct OR results is bounded (~32).
- I was enumerating all subarrays (all dp[i][j]), but the real insight is that for each fixed right endpoint j, the number of distinct OR states is bounded (~32), so the optimization comes from compressing the state space rather than scanning all i.
- Optimal Answer. where $N$ is the length of A, and $W$ is the maximum size of elements in A , TC: $O(n*logW)$ , SC: $O(n*logW)$

🧩 Edit Distance series

Notes
- The overall approach is very similar. All problems can be simplified into a 1D array, but it’s best to start with a 2D array because it’s easier to understand that way.
- DP array using dp[s.length()+1][t.length()+1]: Initialization is more convenient and allows for unified logic handling.
- Operations
  - Delete: LC 392, 115, 583
  - Delete/Insert/Update: LC 72
LC 392. Is Subsequence
- ⚪ Method 1: 2-pointers. Its performance is better DP and it's super easy to implement;
  - Optimal Answer. TC: $O(n)$ , SC: $O(1)$
- Method 2: DP. Need to realize it's very similar to LC 1143.
  - Answer. TC: $O(m*n)$ , SC: $O(min(m,n))$
🔴 LC 115. Distinct Subsequences
- Hint: Only do deletion on String s
- Optimal Answer. TC: $O(m*n)$ , SC: $O(min(m,n))$
LC 583. Delete Operation for Two Strings
- Method 1: Use DP to resolve it directly. Optimal Answer. TC: $O(m*n)$ , SC: $O(min(m,n))$
- Method 2: Use the DP solution of LC 1143 to resolve it
🌟 LC 72. Edit Distance
- Optimal Answer. TC: $O(M*N)$ , SC: $O(min(M,N))$
🟠 LC 97. Interleaving String
- I came up with approach-1 after spending a lot of time, but that's not the best way (the way of defining the state transition function) to solve this problem.
- Assume n1 = length of s1, n2 = length of s2.
- Approach 1 (My solution)
  - TC: $O((n1 + n2)*min(n1, n2))≤O(n1*n2)$ , SC: $O(min(n1, n2))$
- 👍 Approach 2 (LeetCode solution)
  - $TC: O(n1*n2), SC: O(n2)$

🧩 Palindromic String

Notes
- Use dp[i][j] to iterate each substring (s[i] to s[j]) case.
⚪ LC 647. Palindromic Substrings
- Optimal Answer. TC: $O(n^2)$ , SC: $O(n)$
🌟 LC 5. Longest Palindromic Substring
- Optimal Solution. TC: $O(n^2)$ , SC: $O(n)$
🌟 LC 516. Longest Palindromic Subsequence
- Optimal Answer. TC: $O(n^2)$ , SC: $O(n)$
🟠 LC 3472. Longest Palindromic Subsequence After at Most K Operations
- It's a combination of an advanced version of LC 516 + Knapsack ideas
- Optimal Answer. TC: $O(n*n*k)$ , SC: $O(n*n*k)$

DP on Tree

LC 2858. Minimum Edge Reversals So Every Node Is Reachable
- Optimal Answer. TC: $O(n)$ , SC: $O(n)$

PreviousGreedy NextPrefix Sum/Product

Last updated 20 days ago

hashtagNotes

hashtagTypical Questions

hashtagMiscellaneous DP

hashtagPattern Counting

hashtag2D Matrix Problems

hashtagKnapsack Problems

hashtag🧩 0-1 Knapsack Problem

hashtag🧩 Complete Knapsack Problem

hashtagHouse Robber

hashtag🧩 Stock Problems

hashtagSubsequence/Subarray Problems

hashtag🧩 Classic Subsequence/Subarray

hashtag🧩 Edit Distance series

hashtag🧩 Palindromic String

hashtagDP on Tree

Notes

Typical Questions

Miscellaneous DP

Pattern Counting

2D Matrix Problems

Knapsack Problems

🧩 0-1 Knapsack Problem

🧩 Complete Knapsack Problem

House Robber

🧩 Stock Problems

Subsequence/Subarray Problems

🧩 Classic Subsequence/Subarray

🧩 Edit Distance series

🧩 Palindromic String

DP on Tree