Why recursion becomes slow
You're climbing a staircase of
n steps, taking 1 or 2 steps at a time. How many distinct ways reach the top? The recursive answer writes itself: the ways to reach step n is the ways to reach n-1 (then one step) plus the ways to reach n-2 (then two steps) — ways(n) = ways(n-1) + ways(n-2), base cases ways(0) = ways(1) = 1. Correct, elegant… and catastrophically slow.Why? Expand
ways(5) one level at a time and watch the same questions come back:| call | asks for |
|---|---|
ways(5) | ways(4) and ways(3) |
ways(4) | ways(3) (again) and ways(2) |
each ways(3) | ways(2) (again and again) and ways(1) |
ways(3) is computed 2 times, ways(2) 3 times — and the double-counting compounds every level down. The run below counts the actual calls: just 20 stairs already costs 21,891 calls for an answer of 10,946. Double the stairs and the calls don't double — they multiply: this is O(2ⁿ), exponential time (from the Complexity lesson: the bucket that explodes).let calls = 0;
function ways(n) { // the natural recursion, unchanged
calls++;
if (n <= 1) return 1;
return ways(n - 1) + ways(n - 2);
}
console.log(ways(20)); // 10946
console.log(calls); // 21891 (function calls for just 20 stairs)Quick check
Expanding ways(6): predict how many separate times ways(4) gets computed.
Answer it in the interactive lesson to keep your progress.
The two ingredients: overlapping subproblems + optimal substructure
The staircase blow-up has a precise diagnosis, and it names the two properties dynamic programming (DP) needs:
- Overlapping subproblems — the same smaller questions recur.
ways(3)underways(5)is identical toways(3)underways(4); the call tree keeps re-asking it. (Contrast merge sort: its two halves are different subproblems — no overlap, so no DP needed.) - Optimal substructure — the answer to the big question is assembled from answers to the smaller ones.
ways(5)isways(4) + ways(3); nothing else about how those climbs happened matters.
When both hold, the fix is almost embarrassingly simple: compute each distinct subproblem once, store its answer, and reuse it. There are only
n + 1 distinct questions (ways(0) … ways(n)) hiding inside those 21,891 calls — pay for each once and the exponential tree collapses to a straight line, O(n).It's climbing the stairs while jotting each step's route-count on a sticky note — whenever a question repeats, you read the note instead of re-deriving it. The next two sections are the two ways to organize the notes: memoization (top-down) and tabulation (bottom-up).
Quick check
Merge sort splits [8, 3, 5, 1] into [8, 3] and [5, 1]. Predict: is this a DP problem?
Answer it in the interactive lesson to keep your progress.
Memoization: recursion that remembers (top-down)
The first way to organize the sticky notes: keep the recursion exactly as it is, but cache every answer the first time you compute it. Before recursing, check the cache; after computing, store. That's memoization — you met the idea at the end of the Recursion lesson, and here it becomes half of DP.
It's called top-down because you start from the big question and let the recursion discover which subproblems it needs. Here it is on a new problem — counting paths through a
rows × cols grid moving only down or right. Same two ingredients: the count for a cell is built from the two neighbouring counts (optimal substructure), and the same cells are reached by many routes (overlap).Walk the
3×3 call: countPaths(3,3) needs (2,3) and (3,2); both of those need (2,2) — the overlap. With the memo, the second request for (2,2) is a cache read, O(1), and every distinct cell is computed exactly once: O(rows × cols) total instead of exponential.function countPaths(rows, cols, memo = {}) {
if (rows === 1 || cols === 1) return 1;
const key = rows + ',' + cols;
if (memo[key] !== undefined) return memo[key];
memo[key] = countPaths(rows - 1, cols, memo) + countPaths(rows, cols - 1, memo);
return memo[key];
}
console.log('paths in 3x3 grid:', countPaths(3, 3)); // 6
console.log('paths in 3x7 grid:', countPaths(3, 7)); // 28Quick check
With the memo in place, predict the cost of the SECOND time countPaths(2, 2) is needed.
Answer it in the interactive lesson to keep your progress.
Tabulation: build the table bottom-up
The second way: skip the recursion entirely and fill a table from the smallest case up, so that by the time you compute an entry, everything it depends on is already there. That's tabulation — and it comes with the three words every DP conversation uses:
- the state — what one table entry means:
ways[i]= "number of ways to reach stepi" - the transition — the recurrence that fills an entry from earlier ones:
- the base cases — the entries you can write down directly:
ways[0] = 1,ways[1] = 1
Trace it, entry by entry
ways[0] = 1,ways[1] = 1— the base casesways[2] = 1 + 1 = 2ways[3] = 2 + 1 = 3ways[4] = 3 + 2 = 5ways[5] = 5 + 3 = 8
Each entry is computed once, by reading the two before it — 6 additions where the naive recursion made thousands of calls. (Yes — it's the Fibonacci sequence in disguise.) In the animation, watch the table fill left to right: every new cell only ever reads cells already filled, which is exactly what the fill order must guarantee. In JavaScript, one way to write those steps:
This section has a step-by-step animation in the interactive lesson.
function climbStairs(n) {
const ways = new Array(n + 1).fill(0);
ways[0] = 1;
ways[1] = 1;
for (let i = 2; i <= n; i++) {
ways[i] = ways[i - 1] + ways[i - 2];
}
return ways;
}
const stairsTable = climbStairs(6);
console.log('dp table:', stairsTable); // [1,1,2,3,5,8,13]
console.log('ways to climb 6 stairs:', stairsTable[6]); // 13Quick check
Bottom-up Fibonacci can run in O(1) space by…
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Wrong base cases. DP is a tower built on its base; get
ways[0]/ways[1]wrong and every value above is wrong. Nail the smallest cases first, by hand. - Wrong fill order. Bottom-up requires that everything an entry depends on is already computed. If
dp[i]readsdp[i-1], filliascending; a 2-D transition dictates its own order. Fill against the arrows and you read zeros. - Missing the overlap. If subproblems do not actually repeat, DP adds bookkeeping for nothing — plain recursion, divide-and-conquer, or greedy may be the right tool.
- Memoization vs tabulation? Same answers, same complexity. Top-down is quicker to write (add a cache to the recursion you already have) and only visits states that are actually needed; bottom-up avoids recursion depth limits and makes space-squeezing (rolling variables) easy. Knowing both, you choose deliberately.
Quick check
You set ways[1] = 2 by mistake (should be 1). Predict ways[4].
Answer it in the interactive lesson to keep your progress.
From stairs to house robber: adding a decision
Climbing stairs counted possibilities. Most interview DP asks you to choose the best — and the jump is smaller than it looks. Take house robber: houses hold values
[2, 7, 9, 3, 1], you cannot rob two adjacent ones, maximize the take. Same skeleton, one new idea — each entry now records the best decision so far:- state —
best[i]= "most money possible from the firsti+1houses" - transition — at house
i, either skip it (keepbest[i-1]) or rob it (its value plusbest[i-2], since the neighbour is off-limits):best[i] = max(best[i-1], best[i-2] + val[i]) - base cases —
best[0] = val[0],best[1] = max(val[0], val[1])
Trace it on [2, 7, 9, 3, 1]
| house (value) | skip keeps | rob gains | best[i] |
|---|---|---|---|
| 0 (2) | — | — | 2 |
| 1 (7) | 2 | 7 | 7 |
| 2 (9) | 7 | 2 + 9 = 11 | 11 |
| 3 (3) | 11 | 7 + 3 = 10 | 11 |
| 4 (1) | 11 | 11 + 1 = 12 | 12 |
Answer:
12 (rob houses 0, 2, 4). Notice what changed from the staircase: the + in the transition became a max of two choices — that is the entire difference. The Warm-up drills walk this exact ladder (Fibonacci → climb stairs → house robber → knapsack), each one re-using the recipe: state, transition, base cases, fill order.function robPlan(vals) {
const best = [vals[0], Math.max(vals[0], vals[1])];
for (let i = 2; i < vals.length; i++) {
best[i] = Math.max(best[i - 1], best[i - 2] + vals[i]);
}
return best;
}
console.log(robPlan([2, 7, 9, 3, 1])); // [2,7,11,11,12]Quick check
House robber on [5, 1, 1, 5]: predict best[3].
Answer it in the interactive lesson to keep your progress.
Knapsack problems and capacity-based DP
House robber decided rob or skip with one constraint (no neighbours). Promote that to the big leagues: give each item a weight and make the constraint a shared capacity — now the state needs a second dimension, and you have 0/1 knapsack, the template for a huge family of problems.
Many DP problems are built around a capacity, budget, or target. In 0/1 knapsack, each item can be taken or skipped, and the state tracks the best value for a given item count and remaining weight. Subset sum, partition, and many budgeted decisions use the same pattern: choose the best of taking the current item or leaving it behind.
A common recurrence is:
- skip item:
dp[i][w] = dp[i-1][w] - take item:
dp[i][w] = value[i-1] + dp[i-1][w - weight[i-1]](if it fits)
That is the heart of knapsack-style DP: an item dimension plus a capacity dimension, where each state reuses earlier states with smaller capacity or fewer items.
function knapsack01(weights, values, capacity) {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w];
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
dp[i][w],
values[i - 1] + dp[i - 1][w - weights[i - 1]]
);
}
}
}
return dp[n][capacity];
}How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, DP's cost is the number of distinct subproblems times the work per subproblem:
| Problem | States | Work each | Total |
|---|---|---|---|
| climb stairs / house robber | n | O(1) | O(n) |
| grid paths | rows × cols | O(1) | O(rows·cols) |
| coin change | amount | O(coins) | O(amount·coins) |
| 0/1 knapsack | n × W | O(1) | O(n·W) |
- climb stairs / Fibonacci →
O(n)subproblems,O(1)each →O(n)time (vsO(2ⁿ)naive), andO(1)space if you keep only the last two values. - grid paths / coin change →
O(states × choices)— a 2-D table or an amount×coins loop. - 0/1 knapsack / subset sum →
O(n·W)time andO(n·W)space (orO(W)with a rolling array), whereWis the capacity or target.
Key takeaways:
- DP needs overlapping subproblems + optimal substructure.
- Solve each subproblem once: bottom-up tabulation or top-down memoization.
- Cost = states × work-per-state; often the table collapses to a few rolling variables.
This collapses an exponential search into a linear or polynomial table — the boss level of interviews. The classics are now one click away — use the algorithm switcher at the top of this lesson to open each as its own mini-lesson: coin change (fewest coins — in the animation below, watch each
dp[a] cell try every coin and keep the smallest answer + 1), 0/1 knapsack & subset sum (take-it-or-leave-it choices), and longest common subsequence / edit distance (2-D tables). And that completes the path — dynamic programming is the last stop, built on everything before it. From here, the classics in Practice are yours to take apart.This section has a step-by-step animation in the interactive lesson.
function minCoins(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log('min coins for 11 from [1,2,5]:', minCoins([1, 2, 5], 11)); // 3
console.log('min coins for 3 from [2]:', minCoins([2], 3)); // -1