Most of the dynamic programming you’ll meet in an interview reduces to about seven recurrences. The code is rarely the hard part. The hard part is the ninety seconds where you look at a fresh problem and decide what the subproblem is. Name the state correctly and the transition writes itself. Name it wrong and you’ll spend twenty minutes debugging a recursion that double-counts or quietly skips a case.
So the skill worth drilling isn’t memorizing solutions. It’s recognition: reading a prompt and mapping it onto a recurrence you already know cold. These are the ones that keep coming back, and the tells that give each one away.
The signal that a problem is DP at all
Three words in a prompt should make you consider DP: count, minimum or maximum, and can you (as in, is some target reachable). Add a set of choices at each step, plus the risk that a locally good choice hurts you later, and you’re almost certainly looking at DP rather than greedy. The standard sanity check is Coin Change. Greedy grabs the biggest coin first, but with coins of 1, 3, and 4 making 6, greedy takes 4+1+1 for three coins while the real answer is 3+3 for two. When greedy breaks like that, you have to consider every branch, and DP is how you do that without re-solving the same subproblem a million times.
Every recurrence below rests on the same two questions. What does one number in my table mean? And how do I build that number out of smaller ones I’ve already computed? If you can answer those two out loud, you’re most of the way to correct code.
Linear sequence DP: walking an array once
The simplest family. Your state is a single index, and dp[i] depends on a couple of earlier entries, usually dp[i-1] and dp[i-2]. House Robber is the archetype: at each house you either take it and skip the neighbor, or skip it and keep whatever you already had. Climbing Stairs, Decode Ways, and the maximum-subarray flavor of Kadane all live here.
def rob(nums):
take, skip = 0, 0
for n in nums:
take, skip = skip + n, max(take, skip)
return max(take, skip)
You spot this family when the answer at position i is fixed by a small, constant window of positions just behind it. Once you see that, you can throw away the full array and keep two or three rolling variables, which is exactly the space follow-up an interviewer will push you toward.
Choose-or-skip: the knapsack shape
When each item has a weight and you’re filling a budget, the state grows a second dimension: dp[i][w] is the best you can do considering the first i items with capacity w. At each item you either leave it out (dp[i-1][w]) or take it (value plus dp[i-1][w minus weight]). Partition Equal Subset Sum, Target Sum, and the “can you make exactly this total” problems are 0/1 knapsack wearing a costume.
The variant that trips people is bounded versus unbounded. If you can reuse an item as many times as you like, that’s Coin Change and rod cutting, and the loop order changes: you iterate capacity forward so the same coin can be picked again. Getting that loop direction right is one of the few genuinely fiddly things in DP, and interviewers know it, so expect them to ask why the loops are ordered the way they are.
def coin_change(coins, amount):
dp = [0] + [float('inf')] * amount
for c in coins:
for a in range(c, amount + 1):
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Two sequences side by side
Any time the input is two strings or two arrays and you’re comparing them, the state is a pair of indices: dp[i][j] describes the answer for the first i characters of one and the first j of the other. Edit Distance, Longest Common Subsequence, and Distinct Subsequences are all this. The transition compares the current pair of characters. If they match, you extend the diagonal (dp[i-1][j-1]). If they don’t, you take the best of dropping a character from one side or the other.
Recognition gets fast once the shape sticks. Two inputs, a question about aligning or transforming one into the other, and a 2D grid indexed by how far you’ve consumed each. Edit Distance is worth having in your fingers, because its three operations (insert, delete, replace) map cleanly to the three neighbors of a cell.
Grid path DP
An actual grid this time. dp[i][j] is the answer for the cell at row i, column j, built from the cell above and the cell to the left. Unique Paths counts routes, Minimum Path Sum takes the cheaper incoming neighbor, and Dungeon Game runs the recurrence backward from the exit because the constraint (health can never hit zero) forces you to reason from the goal outward. The moment you see a robot, a grid, and movement restricted to right and down, you’re done deciding what the state is.
Interval DP: solve the inside first
Here dp[i][j] covers a subarray or substring from i to j, and you build longer intervals out of shorter ones by choosing a split point k between them. Matrix Chain Multiplication, Burst Balloons, and the “fewest cuts to break a string into palindromes” problems are the canonical set. This family is harder, because the transition adds a third loop over the split point and the fill order matters: you iterate by increasing interval length, not row by row.
Burst Balloons is the one that separates people who’ve drilled interval DP from people who haven’t. The trick is to reason about which balloon you pop last in a range, not first, because the last one still has both boundaries intact. If that inversion feels unnatural when you read it, that’s your signal to practice this pattern on its own rather than hoping to derive it live under pressure.
Longest increasing subsequence and its binary-search shortcut
LIS earns its own mention because it shows up constantly and has two very different solutions. The O(n^2) version defines dp[i] as the length of the longest increasing subsequence ending at index i, and you scan all earlier indices to extend. The O(n log n) version keeps a “tails” array and binary-searches the insertion point, which is a genuinely clever result and a favorite follow-up. Russian Doll Envelopes and Longest Increasing Path in a matrix are LIS in disguise. If a problem asks for the longest chain where each element has to beat the previous one under some ordering, reach for this first.
State-machine DP: when an index isn’t enough
Some problems need more than a position to describe where you are. The Best Time to Buy and Sell Stock series is the cleanest example: your state is the day plus whether you currently hold a share, and you have a small set of transitions between holding and not holding. Add a cooldown or a per-trade fee and you just add states, not thinking. Paint House and any problem that says “you can’t do the same thing twice in a row” belong here too. A phrase like “with cooldown,” “at most k times,” or “no two adjacent” is the tell, quietly adding a dimension to your state.
def max_profit_cooldown(prices):
hold, sold, rest = float('-inf'), 0, 0
for p in prices:
hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
return max(sold, rest)
The recurrence map
One reference for the whole set. Read the state column as a full sentence and the rest tends to follow.
| Pattern | What one dp entry means | How it transitions | Canonical problems | Typical time |
|---|---|---|---|---|
| Linear sequence | dp[i] = best answer up to index i | Combine dp[i-1] and dp[i-2] | House Robber, Climbing Stairs, Decode Ways | O(n) |
| 0/1 knapsack | dp[i][w] = best using first i items at capacity w | Take item i vs skip item i | Partition Equal Subset Sum, Target Sum | O(n·W) |
| Unbounded knapsack | dp[a] = best way to reach amount a | Reuse an item, loop capacity forward | Coin Change, Rod Cutting | O(n·amount) |
| Two-sequence | dp[i][j] = answer for prefixes of length i and j | Match extends the diagonal, else best neighbor | Edit Distance, Longest Common Subsequence | O(m·n) |
| Grid path | dp[i][j] = answer at cell (i, j) | Build from the top and left neighbor | Unique Paths, Minimum Path Sum, Dungeon Game | O(m·n) |
| Interval | dp[i][j] = answer for the range i..j | Split at k, combine the two halves | Burst Balloons, Matrix Chain, Palindrome Partitioning II | O(n^3) |
| Longest increasing subsequence | dp[i] = longest chain ending at index i | Extend from a valid earlier j, or binary-search tails | LIS, Russian Doll Envelopes | O(n^2) or O(n log n) |
| State machine | dp[i][state] = best at step i in a given state | Transition between a small set of states | Buy/Sell Stock with cooldown or fee, Paint House | O(n·states) |
The move that saves interviews is saying the state definition out loud as a complete sentence before you write a single line: “dp of a is the fewest coins that make amount a.” If you can’t finish that sentence, you don’t understand the problem yet, and writing code will only bury the confusion. Start from the plain recursion, add a memo dictionary, and convert to a bottom-up table only if the interviewer asks about the recursion stack or constant space. Most of the time the recursive version with memoization is what they wanted to see anyway, because it proves you found the subproblem, which was the entire point of asking.
Drill the patterns next:
