Pattern Guide
Dynamic Programming
"Overlapping subproblems + optimal substructure = DP."
DP is not magic. It's recursion with memoization, then turned into a table. Learn the 4-step progression from brute force to space-optimized tabulation, and the classic problem families.
24 min readdp problems →
Problems you can solve with this pattern
13 problems · click any to start solving
Step 1 → Brute force recursion
// No memoization. Time: O(2^n)
const helper = (i) => {
if (i >= n) return 0;
return Math.max(helper(i + 1), nums[i] + helper(i + 2));
};Dynamic programming has a reputation for being mysterious, but there's a mechanical progression that works on almost every DP problem. The key is recognizing that DP is just recursion where you cache intermediate results to avoid recomputing them. Once you have the recursive solution, turning it into tabulation is almost mechanical.
Two requirements for DP:
1. Optimal substructure — optimal solution of the whole can be built from optimal solutions of subproblems
2. Overlapping subproblems — same subproblems are solved multiple times in the naive recursion
1. Optimal substructure — optimal solution of the whole can be built from optimal solutions of subproblems
2. Overlapping subproblems — same subproblems are solved multiple times in the naive recursion
The 4-Step Progression
Step 1 → Brute force recursion
// No memoization. Time: O(2^n)
const helper = (i) => {
if (i >= n) return 0;
return Math.max(helper(i + 1), nums[i] + helper(i + 2));
};Step 2 → Memoization (top-down)
// Cache results. Time: O(n), Space: O(n)
const mem = {};
const helper = (i) => {
if (i >= n) return 0;
if (mem[i] !== undefined) return mem[i];
return mem[i] = Math.max(helper(i + 1), nums[i] + helper(i + 2));
};Step 3 → Tabulation (bottom-up)
// Build table iteratively. Time: O(n), Space: O(n)
const dp = new Array(n + 2).fill(0);
for (let i = n - 1; i >= 0; i--)
dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
return dp[0];Step 4 → Space optimization
// Only need last two values. Time: O(n), Space: O(1)
let next1 = 0, next2 = 0;
for (let i = n - 1; i >= 0; i--) {
const curr = Math.max(next1, nums[i] + next2);
next2 = next1;
next1 = curr;
}
return next1;DAG visualization trick: Draw the recursion tree as a DAG (Directed Acyclic Graph) — each unique subproblem is one node. The DAG shape tells you:
- Shape of the DP table (dimensions)
- What subproblems each problem needs
- Rotate DAG 90° clockwise → it looks like the DP table filling order
- Shape of the DP table (dimensions)
- What subproblems each problem needs
- Rotate DAG 90° clockwise → it looks like the DP table filling order
Problem Families
| Family | Key Words | State Shape |
|---|---|---|
| 1D linear | Fibonacci, house robber, climbing stairs | dp[i] |
| 2D grid | Min path, unique paths, coin change (unbounded) | dp[i][j] |
| Knapsack | 0/1 take or skip, weight/value | dp[i][w] |
| Interval DP | Merge, burst, cut, matrix chain | dp[i][j] = range [i..j] |
| Tree DP | House robber III, max path sum | pair [skip, rob] from postorder |
| Bitmask DP | Assigned tasks, TSP | dp[mask][i] |
| Digit DP | Count numbers with property ≤ N | dp[pos][tight][state] |
DP on Strings (Edit Distance Family)
Template — 2D DP on two strings s and t:
``
- If s[i-1] === t[j-1]: dp[i][j] = dp[i-1][j-1] + (something)
- Else: dp[i][j] = min/max of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (cost)
Edit distance, LCS, shortest common supersequence, wildcard matching all use this skeleton.
``
dp[i][j] = answer for s[0..i-1] and t[0..j-1]
- If s[i-1] === t[j-1]: dp[i][j] = dp[i-1][j-1] + (something)
- Else: dp[i][j] = min/max of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (cost)
Edit distance, LCS, shortest common supersequence, wildcard matching all use this skeleton.
DP on Intervals
Interval DP template: dp[i][j] = answer for subproblem on range [i, j].
Fill by increasing length: for len in 2..n → for i in 0..n-len → j = i+len-1 → try all split points k.
Used for: burst balloons, matrix chain multiplication, palindrome partitioning, optimal BST.
Fill by increasing length: for len in 2..n → for i in 0..n-len → j = i+len-1 → try all split points k.
Used for: burst balloons, matrix chain multiplication, palindrome partitioning, optimal BST.
Knapsack Pattern
0/1 Knapsack template: dp[i][w] = max value using first i items with capacity w.
- Include item i: dp[i-1][w-weight[i]] + value[i]
- Exclude item i: dp[i-1][w]
- Take max of both
1D optimization: iterate capacity backwards when each item can only be used ONCE (0/1). Iterate forwards for unbounded knapsack (coin change).
- Include item i: dp[i-1][w-weight[i]] + value[i]
- Exclude item i: dp[i-1][w]
- Take max of both
1D optimization: iterate capacity backwards when each item can only be used ONCE (0/1). Iterate forwards for unbounded knapsack (coin change).
DP pattern families:
- 1D linear: Fibonacci, climbing stairs, house robber, coin change, Kadane's
- 2D grid: unique paths, minimum path sum, dungeon game
- 2D string: edit distance, LCS, regex, wildcard matching
- Interval: burst balloons, matrix chain, palindrome partition
- Knapsack: 0/1 (iterate j backwards), unbounded (forwards), count variants
- Bitmask DP: traveling salesman, min cost to visit all nodes
Recognizing DP: words like *shortest, longest, minimum, maximum, count, ways, best* — especially with a constraint like "at most k" or "contiguous".
Knapsack direction rule: iterate weight/sum backwards for 0/1 (each item once), forwards for unbounded (items reusable).
- 1D linear: Fibonacci, climbing stairs, house robber, coin change, Kadane's
- 2D grid: unique paths, minimum path sum, dungeon game
- 2D string: edit distance, LCS, regex, wildcard matching
- Interval: burst balloons, matrix chain, palindrome partition
- Knapsack: 0/1 (iterate j backwards), unbounded (forwards), count variants
- Bitmask DP: traveling salesman, min cost to visit all nodes
Recognizing DP: words like *shortest, longest, minimum, maximum, count, ways, best* — especially with a constraint like "at most k" or "contiguous".
Knapsack direction rule: iterate weight/sum backwards for 0/1 (each item once), forwards for unbounded (items reusable).