SyntaxPilot
Courses/JavaScript/Lesson 38
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript · Lesson 38 of 40

DSA in JS 5: dynamic programming

queued

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 for a points; Infinity means "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

  1. The question: write it as a function of a number (or a few): ways(n), fewest(amount).
  2. The last choice: express the answer using smaller questions: ways(n - 1) + ways(n - 2); 1 + min(fewest(amount - c)).
  3. The stopping case (base case): the smallest question you can answer directly: ways(1) = 1, fewest(0) = 0.
  4. 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

  1. What is dynamic programming? Solving a problem by breaking it into overlapping subproblems, solving each once, and reusing the stored answers (memoization or tabulation).
  2. What two properties make a problem suitable for DP? Overlapping subproblems and optimal substructure.
  3. 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.
  4. 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.
  5. 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.
  6. What is the complexity of coin change DP? O(amount × number of coins) time, O(amount) memory.
  7. 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.
  8. 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.