HANDS-ON · 120 minutes
The most-feared topic made approachable: memoized recursion → 1D → 2D → interval DP, grounded in retry-cost logic from Brandon's orchestration framework.
Dynamic programming has a reputation that exceeds its difficulty. Once you see that most DP problems are just recursive solutions with a memo table bolted on, the category stops feeling like a special discipline and starts feeling like a pattern you already know.
The clearest version of this insight I had came from the retry logic in my Python orchestration framework. At each step in a job DAG, I needed the minimum number of retries to complete all downstream dependencies. That is a subproblem tree: cost(node) = 1 + min(cost(child) for child in node.children). Once I recognized it as such, memoizing already-computed nodes was obvious. functools.cache made it a one-line addition.
The classic formulation is usually more abstract — climbing stairs, coin change, longest common subsequence — but the thought process is identical: define the state, write the recursive relation in plain English, implement the recursion, add @cache. Only then should you consider converting to an iterative bottom-up table, and only if constraints demand it.
Three tiers cover almost everything:
[i, j]; fill by increasing lengthThe mental model for 1D DP: dp[i] is the answer for the problem restricted to the first i elements (or to amount i). You fill it left to right, using previously computed entries.
dp[amount] = minimum coins to make exactly amount. Recurrence: for each coin c, if c <= i, then dp[i] = min(dp[i], dp[i - c] + 1).
graph LR A["dp[0]=0"] -->|"+coin 2"| B["dp[2]=1"] A -->|"+coin 3"| C["dp[3]=1"] B -->|"+coin 2"| D["dp[4]=2"] B -->|"+coin 3"| E["dp[5]=2"] C -->|"+coin 3"| F["dp[6]=2"] style A fill:#4ade80 style F fill:#4ade80
Adjacent houses cannot both be robbed. dp[i] = maximum money from houses 0..i. At each house, choose: skip it (carry dp[i-1]) or rob it (take nums[i] + dp[i-2]).
Analogy — the garden path: imagine walking a garden path and collecting gems, but the rule is you cannot collect from two adjacent tiles. At each tile, you decide: skip it and keep your prior total, or grab it and add it to the total two steps back. The right choice at every tile is the maximum of those two options.
When this bites: the top-down @cache version of house robber fails when N exceeds Python's default recursion limit (~1000). The iterative bottom-up version above has no such limit. For problems with large N, prefer bottom-up or increase the limit explicitly with sys.setrecursionlimit.
dp[i][j] = length of LCS of s[:i] and t[:j]. If characters match, extend: dp[i][j] = dp[i-1][j-1] + 1. If they don't, take the best of skipping one character from either string.
Space optimization: each row only needs the previous row. Keep two 1D arrays instead of the full M×N table — reducing space from O(M×N) to O(min(M,N)).
dp[i][j] = number of ways to reach cell (i, j) moving only right or down. Every cell in the first row or column has exactly one path (go straight). Every other cell receives paths from above and from the left.
Close the code and try these from memory:
dp[0] = 0 the correct base case, and what would happen if you set dp[0] = float('inf')?s[i-1] != t[j-1], what does max(dp[i-1][j], dp[i][j-1]) represent in plain English?Reflective prompt: The retry-cost problem in my orchestration framework looked like DP, but each node's cost also depended on external state (whether a downstream service was healthy). That breaks the DP assumption of reproducible subproblems. How would you handle DP when subproblems depend on external state that can change? Think about what you would cache, and what you would re-query.
Application-level questions on DP recurrences, memoization, and 1D/2D patterns
1. Before writing any DP code, you should define the state. For 'coin change — minimum coins to reach amount W', what is dp[i]?
Correct Answer: B
dp[i] = minimum coins needed to make exactly amount i. Recurrence: dp[i] = min(dp[i - c] + 1) for each coin c where c <= i. Base: dp[0] = 0. This defines the state before any code is written.
2. You write a recursive DP solution with @functools.cache. Under what conditions should you convert it to a bottom-up table?
Correct Answer: B
@cache is faster to write and often fast enough. Convert to bottom-up when you hit Python's recursion limit (sys.setrecursionlimit is a workaround, not a fix), or when you can roll rows to save space (2D LCS table → two 1D arrays).
3. House Robber: you cannot rob adjacent houses. dp[i] = maximum money from houses 0..i. Which recurrence is correct?
Correct Answer: B
At house i, you either skip it (take dp[i-1]) or rob it (take dp[i-2] + nums[i], because you cannot also rob i-1). The max of those two choices is dp[i]. This is the canonical 1D DP skip-or-take pattern.
4. For Longest Common Subsequence of strings s and t, dp[i][j] is the LCS length for s[:i] and t[:j]. When s[i-1] == t[j-1], what is dp[i][j]?
Correct Answer: B
When s[i-1] matches t[j-1], the current characters extend the LCS of the prefixes before them: dp[i][j] = dp[i-1][j-1] + 1. When they don't match, you take the better of skipping one character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
5. A 2D DP table for LCS of strings of length M and N uses O(M*N) space. How can you reduce this to O(min(M,N))?
Correct Answer: B
Each row dp[i] only depends on dp[i-1]. So you only need two 1D arrays: prev and curr. After computing curr from prev, prev = curr. If you also iterate the shorter string as the inner loop, space is O(min(M,N)).
6. Coin change with denominations [1, 3, 4] and target 6. A greedy (pick largest coin first) gives 4+1+1=3 coins. What is the optimal answer?
Correct Answer: B
DP gives 2 coins: 3+3=6. Greedy gives 3 coins: 4+1+1=6. This is the canonical example where greedy is wrong for arbitrary coin denominations and DP is required. The greedy exchange argument breaks because no coin dominates all combinations.
7. In interval DP, you fill a table where dp[i][j] depends on dp[i][k] and dp[k+1][j] for all k. What loop order is required?
Correct Answer: B
dp[i][j] depends on shorter intervals. Filling by increasing length L guarantees that when you compute dp[i][j] (where j-i+1 == L), all dp[i][k] and dp[k+1][j] (which have length < L) are already computed. Looping on i and j naively does not ensure this.
8. Unique Paths: how many ways to travel from top-left to bottom-right of an M×N grid, moving only right or down? What is the recurrence?
Correct Answer: B
You can reach cell (i,j) from the cell above (i-1,j) or from the left (i,j-1). The number of ways is the sum: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base: first row and column are all 1 (only one way to reach them — go straight right or straight down).
Problem: Given a string s, return the length of the longest palindromic subsequence.
Example: s = "bbbab" — answer is 4 (the subsequence "bbbb").
Hint 1: A palindromic subsequence reads the same forward and backward. LPS of s is the same as the LCS of s and its reverse. Try that first.
Hint 2: Alternatively, define dp[i][j] as the length of the longest palindromic subsequence in s[i..j]. If s[i] == s[j], it extends the inner result: dp[i][j] = dp[i+1][j-1] + 2. Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]). This is interval DP — fill by increasing length.