These are the notes for JavaScript episode 38, the last part of data structures and algorithms. Counting the ways Priya can climb the stairs with plain recursion takes 331 million calls for 40 stairs, because the same smaller questions are solved again and again. A memo (a Map of answers) cuts it to 79 calls: memoization. At the fun-fair coupon counter, the greedy choice (biggest coupon first) pays 11 with three coupons when two are enough, so we try every last choice. Memoized recursion for 100,000 points crashes with Maximum call stack size exceeded, so we fill a table from the bottom: tabulation. Every output below is real Node.js output (Node 24). Times vary from machine to machine; call counts do not.
Builds on: functions (episode 9), errors (13), Map (21), Big O (34), recursion and the call stack (36), sorting (37). Leads to: Capstone: a complete CLI app (39).
Priya's staircase
Priya climbs the stairs one or two steps at a time. In how many different ways can she climb n stairs?
| Stairs | The ways | Count |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1+1, 2 | 2 |
| 3 | 1+1+1, 1+2, 2+1 | 3 |
| 4 | 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 | 5 |
The key thought: her last move was either 1 step (from stair n − 1) or 2 steps (from stair n − 2). So
ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = ways(1) = 1.
These are the Fibonacci numbers, shifted by one.
The obvious attempt: plain recursion
let calls = 0;
function ways(n) {
calls++;
if (n <= 1) return 1;
return ways(n - 1) + ways(n - 2);
}
for (const n of [3, 4, 10, 30, 40]) {
calls = 0;
console.time(`ways(${n})`);
const w = ways(n);
console.timeEnd(`ways(${n})`);
console.log(` ${w} ways, ${calls.toLocaleString("en-US")} calls`);
}
Output (times vary):
ways(3): 0.071ms
3 ways, 5 calls
ways(4): 0.011ms
5 ways, 9 calls
ways(10): 0.01ms
89 ways, 177 calls
ways(30): 15.88ms
1346269 ways, 2,692,537 calls
ways(40): 1.177s
165580141 ways, 331,160,281 calls
The answers are right, but the work explodes: 10 more stairs (30 → 40) means 123 times more calls. Each call makes two more calls, so the work grows roughly like 1.6ⁿ: exponential time, often written as O(2ⁿ). ways(50) would take minutes, ways(100) longer than a lifetime.
Why it explodes: overlapping subproblems
const count = new Map();
function ways(n) {
count.set(n, (count.get(n) || 0) + 1);
if (n <= 1) return 1;
return ways(n - 1) + ways(n - 2);
}
ways(30);
for (const n of [28, 25, 20, 10, 2]) {
console.log(`ways(${n}) was solved ${count.get(n).toLocaleString("en-US")} times`);
}
Output:
ways(28) was solved 2 times
ways(25) was solved 8 times
ways(20) was solved 89 times
ways(10) was solved 10,946 times
ways(2) was solved 514,229 times
ways(30) asks for ways(29) and ways(28); ways(29) asks for ways(28) again, and so on. The smaller questions overlap, and nobody remembers their answers. Problems built from overlapping subproblems are what dynamic programming is for.
Memoization: write the answer down
A teacher who works out 17 × 23 once writes the answer in the margin and just reads it for the next twenty students. In code: before solving n, check a notebook; after solving it, write the answer down. A Map is the notebook.
let calls = 0;
const memo = new Map();
function ways(n) {
calls++;
if (n <= 1) return 1;
if (memo.has(n)) return memo.get(n);
const answer = ways(n - 1) + ways(n - 2);
memo.set(n, answer);
return answer;
}
for (const n of [10, 40, 70]) {
memo.clear();
calls = 0;
console.log(`ways(${n}) = ${ways(n)}, ${calls} calls`);
}
Output:
ways(10) = 89, 19 calls
ways(40) = 165580141, 79 calls
ways(70) = 308061521170129, 139 calls
Each n is now solved once (about 2n calls in total): O(n) time, O(n) memory for the memo. Caching a function's answers by its arguments is called memoization. (ways(80) and above exceed Number.MAX_SAFE_INTEGER, 2⁵³ − 1; use BigInt from episode 2 for exact huge answers.)
When greedy fails: the fun-fair coupon counter
Coupons are worth 9, 6, 5 and 1 points. A ride costs 11. Pay with as few coupons as possible.
Greedy means taking the choice that looks best right now: the biggest coupon that still fits.
const coupons = [9, 6, 5, 1];
function greedy(amount) {
const used = [];
for (const c of coupons) {
while (amount >= c) { used.push(c); amount -= c; }
}
return used;
}
console.log("11:", greedy(11));
console.log("12:", greedy(12));
Output:
11: [ 9, 1, 1 ]
12: [ 9, 1, 1, 1 ]
But 11 = 6 + 5 (two coupons) and 12 = 6 + 6 (two coupons). Greedy never rethinks an early choice: taking the 9 left 2 points that only 1s can pay. (For Indian coins 1, 2, 5, 10, greedy happens to give the best answer; for arbitrary values it does not.)
Try every last choice, and remember
Whatever the best way is, the last coupon is a 9, 6, 5 or 1. If it is c, the rest is the best way to pay amount - c:
fewest(amount) = 1 + min over every coupon c ≤ amount of fewest(amount - c), with fewest(0) = 0.
const coupons = [9, 6, 5, 1];
const memo = new Map();
function fewest(amount) {
if (amount === 0) return 0;
if (memo.has(amount)) return memo.get(amount);
let best = Infinity;
for (const c of coupons) {
if (c <= amount) best = Math.min(best, 1 + fewest(amount - c));
}
memo.set(amount, best);
return best;
}
console.log("11:", fewest(11));
console.log("12:", fewest(12));
Output:
11: 2
12: 2
Infinity is a safe starting value for "the smallest so far": any real count is smaller.
Too deep for the call stack
// fewest as above
console.log("100000:", fewest(100000));
Output:
11: 2
12: 2
main.js:3
function fewest(amount) {
^
RangeError: Maximum call stack size exceeded
at fewest (main.js:3:16)
at fewest (main.js:8:48)
...
fewest(100000) calls fewest(99999), which calls fewest(99998), … about 100,000 calls waiting at once. The call stack (where waiting calls are kept, episode 36) has limited room. The memo stopped the repeats, but not the depth.
Tabulation: fill a table from the bottom
Recursion works top-down: it starts at 100,000 and digs to 0 before anything finishes. Flip it: work out 0, then 1, then 2, … up to 100,000, keeping the answers in an array. When we reach any amount, every smaller answer is already there. It's a plain loop, so there is no deep stack.
const coupons = [9, 6, 5, 1];
function fewest(amount) {
const best = new Array(amount + 1).fill(Infinity);
const last = new Array(amount + 1).fill(0);
best[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coupons) {
if (c <= a && best[a - c] + 1 < best[a]) {
best[a] = best[a - c] + 1;
last[a] = c;
}
}
}
const used = [];
for (let a = amount; a > 0; a -= last[a]) used.push(last[a]);
return { count: best[amount], used };
}
console.log("11:", fewest(11));
console.log("12:", fewest(12));
console.log("100000:", fewest(100000).count);
Output:
11: { count: 2, used: [ 6, 5 ] }
12: { count: 2, used: [ 6, 6 ] }
100000: 11112
best[a]= the fewest coupons forapoints;Infinitymeans "not payable yet".last[a]remembers which coupon gave that best answer, so we can walk back from the amount and list the coupons.- Time: amount × number of coupons = O(amount × coupons); memory O(amount).
The first 12 rows of the table:
| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| best[a] | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 1 | 2 | 2 | 2 |
| last[a] | 1 | 1 | 1 | 1 | 5 | 6 | 6 | 6 | 9 | 9 | 6 | 6 |
Memoization vs tabulation
| Memoization (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| how | recursion + a Map of answers |
a loop filling an array |
| order | starts at the big question | starts at the smallest question |
| solves | only the subproblems it needs | every subproblem up to n |
| deep inputs | can hit Maximum call stack size exceeded |
no recursion, no stack limit |
| easiest to write | yes, add 2 lines to the recursion | needs the right loop order |
The dynamic programming recipe
- The question: write it as a function of a number (or a few):
ways(n),fewest(amount). - The last choice: express the answer using smaller questions:
ways(n - 1) + ways(n - 2);1 + min(fewest(amount - c)). - The stopping case (base case): the smallest question you can answer directly:
ways(1) = 1,fewest(0) = 0. - Remember: a memo, or a table filled from the bottom.
A problem needs DP when it has overlapping subproblems and optimal substructure (the best answer is built from the best answers of smaller pieces). Classic DP problems: climbing stairs, coin change, knapsack, longest common subsequence, edit distance (spell checkers), house robber.
Common mistakes (and what really happens)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| plain recursion on overlapping subproblems | ways(40): 331,160,281 calls, over a second |
the same subproblem solved again and again | a memo (Map) |
| checking the memo but never filling it | still millions of calls | forgot memo.set |
save the answer before returning |
| one memo shared by different inputs (e.g. different coupon lists) | wrong answers | old answers belong to another problem | a new memo per problem, or include the input in the key |
| greedy: biggest coupon first | 11: [ 9, 1, 1 ] |
an early choice is never rethought | try every last choice (DP) |
| deep memoized recursion | RangeError: Maximum call stack size exceeded |
about 100,000 waiting calls | tabulation, bottom-up |
| a table without its base value | every answer is Infinity |
nothing to build on | best[0] = 0 |
new Array(n).fill([]) for a 2D table |
every row is the same array | fill puts the same object in every slot |
Array.from({ length: n }, () => []) |
Mini project: a spell checker with edit distance
How many single-letter edits (insert, delete, replace) turn one word into another? dp[i][j] = the distance between the first i letters of a and the first j letters of b. The last choice: if the last letters match, no edit; otherwise 1 + the best of delete, insert or replace.
function editDistance(a, b) {
const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
for (let i = 0; i <= a.length; i++) dp[i][0] = i; // delete all of a
for (let j = 0; j <= b.length; j++) dp[0][j] = j; // insert all of b
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
return dp[a.length][b.length];
}
const words = ["paneer", "pakora", "paratha", "samosa", "biryani"];
function suggest(typed) {
return words.toSorted((x, y) => editDistance(typed, x) - editDistance(typed, y))[0];
}
console.log(editDistance("panner", "paneer"));
console.log(editDistance("kitten", "sitting"));
for (const t of ["panner", "samsoa", "biriyani", "parata"]) console.log(t, "->", suggest(t));
Output:
1
3
panner -> paneer
samsoa -> samosa
biriyani -> biryani
parata -> paratha
Time O(length of a × length of b). This is how "did you mean …?" suggestions start.
Practice
1. Stairs with steps of 1, 2 or 3: write ways3(n).
Solution
const memo = new Map();
function ways3(n) {
if (n < 0) return 0;
if (n === 0) return 1;
if (memo.has(n)) return memo.get(n);
const answer = ways3(n - 1) + ways3(n - 2) + ways3(n - 3);
memo.set(n, answer);
return answer;
}
console.log(ways3(3), ways3(4), ways3(10), ways3(30));
Output:
4 7 274 53798080
n < 0 returns 0 (overshooting the top is not a way), n === 0 returns 1 (standing at the top is one way).
2. Count all the ways (not the fewest) to pay 11 with coupons 9, 6, 5, 1, where order doesn't matter.
Solution
function countWays(amount, coupons) {
const ways = new Array(amount + 1).fill(0);
ways[0] = 1;
for (const c of coupons) {
for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
}
return ways[amount];
}
console.log(countWays(11, [9, 6, 5, 1]));
console.log(countWays(10, [1, 2, 5, 10]));
Output:
6
11
The six ways: 9+1+1, 6+5, 6+1+1+1+1+1, 5+5+1, 5+six 1s, eleven 1s. Putting the coupon loop outside counts each combination once; with the amount loop outside you would count orders (1+5 and 5+1) separately.
3. Rewrite ways(n) bottom-up with just two variables.
Solution
function ways(n) {
let prev = 1, cur = 1; // ways(0), ways(1)
for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur];
return cur;
}
console.log(ways(5), ways(40), ways(70));
Output:
8 165580141 308061521170129
Each step only needs the last two answers, so the table shrinks to two variables: O(n) time, O(1) memory.
4. House robber: houses in a row hold some money; you can't take two neighbours. What is the most you can take?
Solution
function rob(houses) {
let skip = 0, take = 0; // best so far if we skip / take the last house
for (const money of houses) {
[skip, take] = [Math.max(skip, take), skip + money];
}
return Math.max(skip, take);
}
console.log(rob([20, 50, 10, 40]));
console.log(rob([60, 10, 10, 60, 10]));
Output:
90
120
The last choice for each house: skip it (keep the best so far) or take it (only allowed if the previous one was skipped). 50 + 40 = 90; 60 + 60 = 120.
Quick quiz
const dp = [1, 1];
for (let n = 2; n <= 5; n++) {
dp[n] = dp[n - 1] + dp[n - 2];
}
console.log(dp[5]);
A. 5 B. 8 C. 13 D. 3
Answer
B: 8. The table grows 1, 1, 2, 3, 5, 8: the stairs problem bottom-up, 8 ways to climb 5 stairs. Node really prints 8.
Interview questions
- What is dynamic programming? Solving a problem by breaking it into overlapping subproblems, solving each once, and reusing the stored answers (memoization or tabulation).
- What two properties make a problem suitable for DP? Overlapping subproblems and optimal substructure.
- Memoization vs tabulation? Memoization is top-down recursion with a cache, solving only the needed subproblems; tabulation is bottom-up iteration over a table, with no recursion depth limit.
- Why is naive recursive Fibonacci slow, and how fast is the DP version? It recomputes the same values exponentially many times (about 1.6ⁿ calls); DP is O(n) time, and O(1) memory with two variables.
- Why doesn't greedy work for coin change in general? A locally best choice can force a worse total (9+1+1 vs 6+5); greedy works only for special coin systems like 1, 2, 5, 10.
- What is the complexity of coin change DP? O(amount × number of coins) time, O(amount) memory.
- How do you recover the actual choices, not just the best count? Store which choice produced each best value (
last[a]) and walk back from the target. - What happens with deep recursion in JavaScript?
RangeError: Maximum call stack size exceeded; convert to an iterative, bottom-up solution.
Glossary
| Term | Meaning | Example |
|---|---|---|
| dynamic programming (DP) | solve overlapping subproblems once and reuse the answers | stairs, coupons |
| subproblem | a smaller version of the same question | ways(28) inside ways(30) |
| overlapping subproblems | the same subproblem is needed many times | ways(2) solved 514,229 times |
| optimal substructure | the best answer is built from best answers of smaller parts | 1 + fewest(amount - c) |
| recurrence | a formula for the answer in terms of smaller answers | ways(n) = ways(n - 1) + ways(n - 2) |
| base case | the smallest question answered directly | fewest(0) = 0 |
| exponential time, O(2ⁿ) | work multiplies with each step of n | 331 million calls for 40 stairs |
| memo / memoization | a cache of a function's answers by argument | memo.set(n, answer) |
| cache | stored results to avoid recomputing | the teacher's margin |
| top-down | start at the big question and recurse down | memoized ways |
| bottom-up | start at the smallest question and build up | the best table |
| tabulation | filling a table bottom-up | best[a] for a = 1 … 100000 |
| greedy algorithm | always take the choice that looks best now | biggest coupon first |
Infinity |
a number larger than every other number | "not payable yet" |
| call stack | where waiting function calls are kept | the RangeError trace |
RangeError: Maximum call stack size exceeded |
too many nested calls at once | fewest(100000) recursive |
| Fibonacci numbers | 1, 1, 2, 3, 5, 8, 13, … each is the sum of the two before | the stairs answers |
| edit distance | fewest single-letter edits between two words | panner → paneer: 1 |
| house robber | max sum without taking two neighbours | [20, 50, 10, 40] → 90 |
Summary
- Plain recursion on overlapping subproblems explodes: 331,160,281 calls for 40 stairs.
- Memoization stores each answer in a
Map, so every subproblem is solved once: 79 calls, O(n). - Greedy looks best now but can be wrong: 9+1+1 vs 6+5. DP tries every last choice.
- Very deep recursion crashes with
Maximum call stack size exceeded; tabulation fills a table from the bottom with a loop instead. - The recipe: question → last choice → base case → remember.
- Next: the capstone, a complete command line app that uses the whole course.