Dynamic Programming
Dynamic programming (DP) solves problems by breaking them into subproblems, solving each subproblem once, and storing the result. The stored results are reused instead of recomputed — this is the entire trick.
Two properties must hold for DP to apply:
1. Overlapping Subproblems The same smaller problem is solved multiple times during recursion. Fibonacci(5) calls Fibonacci(3) which calls Fibonacci(1) — and so does Fibonacci(4).
2. Optimal Substructure The optimal solution to a problem can be constructed from optimal solutions to its subproblems. The shortest path from A to C through B is the shortest path A→B plus shortest path B→C.
Recognizing DP Problems
DP problems typically share these signals:
The problem asks for an optimal value (min/max/count)
You need to make a series of choices and each choice affects future choices
The phrase "how many ways" or "minimum cost" or "maximum profit" appears
Brute force would re-solve the same sub-case many times
The problem can be phrased as "what is the best decision at each step?"
Constraints suggest O(n²) or O(n·W) is acceptable (n ≤ 1000, W ≤ 10000)
Fibonacci: The Four Stages
Fibonacci illustrates the evolution from naive recursion to optimal DP. F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).
// Stage 1: Naive Recursion — O(2^n) time, O(n) space (call stack)
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// fibNaive(40) makes ~3 billion calls — unusably slow
// Stage 2: Memoization (top-down DP) — O(n) time, O(n) space
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n); // cache hit
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result); // store before returning
return result;
}
// Stage 3: Tabulation (bottom-up DP) — O(n) time, O(n) space
function fibTab(n) {
if (n <= 1) return n;
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // build from smaller subproblems
}
return dp[n];
}
// Stage 4: Space-optimized — O(n) time, O(1) space
function fibOptimal(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
console.log(fibOptimal(10)); // 55
console.log(fibOptimal(50)); // 12586269025Approach | Time | Space | Notes |
|---|---|---|---|
Naive recursion | O(2^n) | O(n) | Exponential — unusable for n > 40 |
Memoization | O(n) | O(n) | Top-down; natural recursive style |
Tabulation | O(n) | O(n) | Bottom-up; no recursion overhead |
Space-optimized | O(n) | O(1) | Only need last 2 values |
Defining the DP State
The hardest part of DP is defining the state: what does dp[i] represent?
A clear state definition unlocks everything else:
- The base cases become obvious
- The recurrence relation follows naturally
- The final answer is dp[some specific index]
Process:
- Define dp[i] precisely in English
- Write the recurrence (how dp[i] depends on smaller indices)
- Initialize base cases (usually dp[0] or dp[1])
- Fill the table in dependency order (usually left to right)
- Return the target cell
Climbing Stairs
You can climb 1 or 2 steps at a time. How many distinct ways can you reach the top of n stairs?
State: dp[i] = number of ways to reach step i Recurrence: dp[i] = dp[i-1] + dp[i-2] (came from i-1 with a 1-step, or from i-2 with a 2-step) Base cases: dp[1] = 1, dp[2] = 2
// Climbing Stairs — O(n) time, O(1) space
function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Generalization: k step sizes allowed
function climbStairsK(n, k) {
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // one way to be at the ground (do nothing)
for (let i = 1; i <= n; i++) {
for (let step = 1; step <= k && step <= i; step++) {
dp[i] += dp[i - step];
}
}
return dp[n];
}
console.log(climbStairs(5)); // 8
console.log(climbStairsK(5, 3)); // 13 (can take 1, 2, or 3 steps)Coin Change
Given coin denominations and a target amount, find the minimum number of coins to make that amount.
State: dp[i] = minimum coins needed to make amount i Recurrence: dp[i] = min over all coins c: dp[i - c] + 1 (if i - c >= 0) Base cases: dp[0] = 0 (zero coins needed for amount 0) Answer: dp[amount] (or -1 if still Infinity)
// Coin Change — O(amount · coins) time, O(amount) space
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 5, 6, 9], 11)); // 2 (5+6)
console.log(coinChange([2], 3)); // -1 (impossible)
console.log(coinChange([1, 2, 5], 11)); // 3 (5+5+1)House Robber
Houses are arranged in a line. Each house has a value. You cannot rob two adjacent houses. Maximize the total amount robbed.
State: dp[i] = maximum money robbing from houses 0 through i Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- dp[i-1]: skip house i
- dp[i-2] + nums[i]: rob house i (and skip house i-1)
// House Robber — O(n) time, O(1) space
function rob(nums) {
if (nums.length === 1) return nums[0];
let prev2 = 0;
let prev1 = 0;
for (const num of nums) {
const curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// House Robber II — circular (first and last house are adjacent)
function robCircular(nums) {
if (nums.length === 1) return nums[0];
// Rob houses 0..n-2 OR houses 1..n-1 (can't rob both first and last)
function robLinear(arr) {
let prev2 = 0, prev1 = 0;
for (const num of arr) {
const curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
return Math.max(
robLinear(nums.slice(0, nums.length - 1)),
robLinear(nums.slice(1))
);
}
console.log(rob([2, 7, 9, 3, 1])); // 12 (2+9+1)
console.log(robCircular([2, 3, 2])); // 3
console.log(robCircular([1, 2, 3, 1])); // 4The State Definition Process in Practice
Here is a systematic way to arrive at the correct state definition:
Step 1 — Identify what changes between subproblems In Coin Change, the "amount remaining" changes. That becomes the DP index.
Step 2 — What do you want to compute for each state? "Minimum coins to make amount i" — that is dp[i].
Step 3 — How does the answer for state i depend on smaller states? If you use coin c, you reduce to dp[i - c]. Then add 1 for the coin used.
Step 4 — What are the base cases? dp[0] = 0. Any state where the answer is trivially known.
Step 5 — In what order should you fill the table? For Coin Change, left to right — dp[i] depends on dp[i-c] where c > 0, so smaller indices are computed first.
Classic DP Problem Map
Problem | State | Recurrence | Time |
|---|---|---|---|
Fibonacci | dp[i] = fib(i) | dp[i-1] + dp[i-2] | O(n) |
Climbing Stairs | dp[i] = ways to reach i | dp[i-1] + dp[i-2] | O(n) |
Coin Change | dp[i] = min coins for amount i | min(dp[i-c]+1) | O(n·W) |
House Robber | dp[i] = max rob up to i | max(dp[i-1], dp[i-2]+val) | O(n) |
Longest Inc. Subseq. | dp[i] = LIS ending at i | max(dp[j]+1) for j < i | O(n²) |
0/1 Knapsack | dp[i][w] = max value | max(skip, take) | O(n·W) |
Edit Distance | dp[i][j] = ops to convert | 1 + min(3 ops) | O(m·n) |
DP vs Greedy vs Divide and Conquer
Criterion | DP | Greedy | D&C |
|---|---|---|---|
Subproblems | Overlapping | Non-overlapping | Non-overlapping |
Choices | All explored via table | One irrevocable choice | Split evenly |
Correctness | Always (right recurrence) | Only with greedy choice prop. | Always |
Typical complexity | O(n²) – O(n·W) | O(n log n) | O(n log n) |
Confirm the problem has overlapping subproblems and optimal substructure
Write the brute-force recursive solution first — see the overlapping calls
Add a memo table to the recursive solution (top-down DP)
Convert to bottom-up tabulation for better constants and no stack overflow risk
Optimize space by keeping only the rows/values you actually need