My first DP course taught me to "think recursively, memoize, then optimize." That's true but useless at interview speed, because it forces you to derive the structure from scratch every time. What actually works: there are ~4 recurring DP shapes. Recognize the shape, and the recurrence is nearly given.
The Universal Template
Every DP problem answers: "What choice do I make at step i, and what does it cost given the best result up to i-1?"
dp[i] = best result using first i items
choice: take item i β dp[i-1] + value(i)
skip item i β dp[i-1]
dp[i] = max/take of the choices
Everything below is this template wearing different clothes.
Pattern 1: 1D Sequence (Knapsack Family)
Shape: items in a line, one decision per item, a constraint (capacity).
int knapsack(int W, vector<int>& wt, vector<int>& val) {
vector<int> dp(W + 1, 0);
for (int i = 0; i < wt.size(); i++) {
for (int w = W; w >= wt[i]; w--)
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
}
return dp[W];
}
The details that trip people up:
- Reverse iteration = 0/1 (each item once); forward iteration = unbounded (item reusable)
dp[w] means "best value with capacity exactly w available" β the state is the constraint
Family: coin change, subset sum, partition equal subset, rod cutting.
[!TIP]
- If the constraint is a sum (capacity), the DP dimension is the sum. If the constraint is a count (exactly k), the dimension is k. Pick the smaller one as the inner loop.
Pattern 2: 2D Grid
Shape: positions on a grid, moves to neighbors, dp[x][y] = best way to reach (x, y).
int minPathSum(vector<vector<int>>& g) {
int R = g.size(), C = g[0].size();
vector<vector<int>> dp(R, vector<int>(C));
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (!r && !c) dp[r][c] = g[r][c];
else {
int best = INT_MAX;
if (r > 0) best = min(best, dp[r-1][c]);
if (c > 0) best = min(best, dp[r][c-1]);
dp[r][c] = g[r][c] + best;
}
}
return dp[R-1][C-1];
}
Family: unique paths (count instead of min), dungeon game (reverse the direction), longest increasing subsequence in a grid, word break on a board.
The recognition cue: "you're at a cell, you came from above or left" is 2D grid, full stop.
Pattern 3: Subsequence (Two Strings / Two Sequences)
Shape: two sequences, decisions about aligning them: match, skip in A, skip in B.
int lcs(string& a, string& b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (a[i-1] == b[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
return dp[m][n];
}
The three-way choice is the signature: match (diagonal), skip A (up), skip B (left). Family: edit distance (substitution is a fourth move), LCS, interleaving strings, distinct subsequences.
Pattern 4: Intervals (Overlapping Ranges)
Shape: problems defined over ranges β dp[i][j] = best for substring/range [i..j].
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++)
for (int i = 0; i + len <= n; i++)
for (int k = i; k < i + len - 1; k++)
dp[i][i+len-1] = min(dp[i][i+len-1],
dp[i][k] + dp[k+1][i+len-1] + cost(i, k, i+len-1));
The recognition cue: "the answer for a range depends on smaller ranges inside it." Iterate by range length, never by index alone.
The Recognition Flowchart
One array, constraint on sum/count? β PATTERN 1 (knapsack)
Position on a grid, moves between cells? β PATTERN 2 (grid)
Two sequences being aligned? β PATTERN 3 (subsequence)
Answer defined over a range/subset? β PATTERN 4 (intervals)
Space Optimization (The Follow-Up They Always Ask)
| Pattern | 2D table β | How |
|---|
| Knapsack | 1D array, iterate backwards | Each item updates in place |
| Grid | 1D row, O(min(R,C)) | Only previous row needed |
| LCS | 1D with a prev variable | Diagonal value saved before overwrite |
| Intervals | rarely reducible | State genuinely 2D |
[!WARNING]
- Backwards vs forwards is the most common off-by-one killer in knapsack DP. If the item can only be used once, iterate the capacity dimension in reverse β forward iteration silently becomes the unbounded variant.
Practice Order That Actually Works
- Knapsack β coin change β subset sum (P1 until boring)
- Unique paths β min path sum (P2)
- LCS β edit distance (P3)
- Matrix chain (P4)
Each family is one shape with different "value" functions. Master the shape once; the family is pattern-matching.
Discussion (0)
Sign in or create an account to join the discussion.
No comments yet. Start the discussion.