Pattern Reference
Dynamic Programming
"Memoization, tabulation, state definition, transitions. The universal hammer for optimal substructure."
Loading...6 variations
Variations
One core pattern - multiple approaches. Each variation solves a different set of problems.
Loading problems…
Deep Dive Tutorial
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.
key
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;lightbulb
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] |
Worked Problems
DP on Strings (Edit Distance Family)
key
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
lightbulb
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
key
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).
lightbulb
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).