Dynamic Programming From Recursion

The same work, again and again

Part 14 is about one big idea: dynamic programming (DP). DP is a method that solves a problem by splitting it into smaller versions of itself, solving each small version only once, and saving its answer. The name sounds grand, but it is just “recursion that remembers”. Recursion means a function that calls itself. You break a problem into smaller copies of itself, as in Part 8. But you never solve the same small copy twice.

Lesson 32 introduced recursion trees, where every call is drawn as a box (a node). Here is the plain Fibonacci function. In Fibonacci, each number is the sum of the two numbers before it. This version also counts how many calls it makes:

let calls = 0;function fib(n) {                            // fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2)  calls++;  if (n <= 1) return n;                      // base cases  return fib(n - 1) + fib(n - 2);}console.log(fib(20), calls); // 6765 21891

To compute fib(20), the function runs 21,891 times. For 30 it is much worse:

let calls = 0;function fib(n) {  calls++;  return n <= 1 ? n : fib(n - 1) + fib(n - 2);}console.log(fib(30), calls); // 832040 2692537

That is nearly 2.7 million calls for the 30th term. Each call to fib(n) starts two more calls, so the tree about doubles at each level. The reason is easy to see in the tree. fib(5) calls fib(4) and fib(3), but fib(4) also calls fib(3). So the fib(3) part of the tree is built twice, and inside it fib(2) is built again and again. There are only n + 1 different questions, but we answer them an enormous number of times (exponentially many).

Two properties that make DP work

DP works when a problem has both of these properties:

A subproblem is just “the same question with a smaller input”. Sometimes subproblems do not overlap. Merge sort's two halves never share work, so saving answers does nothing, and plain divide and conquer (split, solve each part, join) is the right tool. If subproblems do overlap, DP turns a very slow (exponential, like 2ⁿ) solution into a fast (polynomial, like n or n²) one.

The four questions

Every DP solution answers the same four questions. Write them down before you write any code:

1. State. Which few values pick out one subproblem? (For Fibonacci: just i.)
2. Transition. How do you build the answer for a state from the answers to smaller states?
3. Base cases. Which states have an answer right away, with no recursion?
4. Order. In what order should you fill the states, so that everything a state needs is already known? (For most 1-D problems: from small to large.)

When you can write the transition as a formula, the three ways of coding it below are mostly a copy of the formula into code.

Step 1: plain recursion

Always start here. Write the recursion that is clearly correct, even if it is slow. It is your plan for the solution, and it shows you the state and the transition. The Fibonacci function at the top of this lesson is already this first step. (The brute-force coin counter in lesson 47 is another one: “try every first coin”.)

Step 2: memoization (top-down)

Memoization is a technique that saves (remembers) the result of each call, so the same call is never worked out twice. The word comes from “memo”, a note to yourself. It is not “memorization”. You keep the recursion exactly as it was and add a notebook. Before you work out a state, look it up in the notebook. After you work it out, write it down. The notebook is called a cache: a place where you store answers you already worked out, so you can reuse them. It is usually a Map (lesson 32 used the same trick) or an array indexed by the state. It is called top-down because you start from the big question and let the recursion find the smaller ones.

let calls = 0;function fibMemo(n, memo = new Map()) {  calls++;  if (n <= 1) return n;                      // base cases  if (memo.has(n)) return memo.get(n);       // already solved: reuse the answer  const answer = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);  memo.set(n, answer);                       // write the answer down before returning  return answer;}console.log(fibMemo(30), calls); // 832040 59calls = 0;console.log(fibMemo(50), calls); // 12586269025 99

Now fibMemo(30) makes 59 calls instead of 2.7 million. Why 59? Each of the 29 states from 2 to 30 does real work only once (that is 29 calls that go on to call more). Each of those makes two calls, 58 in total. Add the first call: 1 + 58 = 59. In general it is about 2n calls, so the time is O(n). The notebook uses O(n) space, and the recursion depth is O(n) too.

Traced: climbing stairs with a cache

Here is the stairs problem you will meet soon. ways(n) counts the ways to climb n stairs if you take 1 or 2 steps at a time. Watch the notebook fill up. Look for the cache hits. These are the moments when a whole branch of the tree is skipped.

▶const memo = new Map();2function ways(n) {3  if (n <= 1) return 1;4  if (memo.has(n)) return memo.get(n);5  const result = ways(n - 1) + ways(n - 2);6  memo.set(n, result);7  return result;8}9ways(5);

Step 3: tabulation (bottom-up)

Tabulation goes the other way. Skip the recursion. Make a table dp (a plain array) and fill in the base cases. Then loop from small states to large ones, so every value you need is already in the table. This is called bottom-up.

function fibTab(n) {  if (n <= 1) return n;  const dp = new Array(n + 1).fill(0);       // dp[i] = fib(i)  dp[0] = 0;                                 // base cases first  dp[1] = 1;  for (let i = 2; i <= n; i++) {             // fill in an order where the inputs already exist    dp[i] = dp[i - 1] + dp[i - 2];  }  return dp[n];}console.log(fibTab(10)); // 55console.log(fibTab(50)); // 12586269025

There is no call stack to overflow (the call stack is the computer's list of unfinished function calls), and the loop is short and fast. The cost is that you must get the order right yourself. Also, you fill every entry, even if the final answer needs only some of them.

Step 4: reducing space

Look at the transition: dp[i] reads only dp[i-1] and dp[i-2]. Older entries are never used again, so the full table wastes space. Keep only the last two values:

function fibSpace(n) {  if (n <= 1) return n;  let prev = 0, curr = 1;                    // fib(i-2) and fib(i-1): all that the next value needs  for (let i = 2; i <= n; i++) {    [prev, curr] = [curr, prev + curr];      // slide the window one step to the right  }  return curr;}console.log(fibSpace(10)); // 55console.log(fibSpace(50)); // 12586269025

Climbing stairs and minimum cost

Climbing stairs: you can take 1 or 2 steps at a time. In how many different ways can you reach step n? Your last move was either a 1-step from step n − 1 or a 2-step from step n − 2. These two cases never overlap, so ways(n) = ways(n-1) + ways(n-2). It is Fibonacci in disguise, but with different base cases. There is one way to reach step 0 (do nothing) and one way to reach step 1.

// Climbing stairs: each move is 1 or 2 steps. In how many ways can you reach step n?// ways(n) = ways(n-1) + ways(n-2): your last move was a 1-step from n-1, or a 2-step from n-2.function waysMemo(n, memo = new Map()) {     // top-down  if (n <= 1) return 1;                      // one way to stand still, one way to reach step 1  if (memo.has(n)) return memo.get(n);  const answer = waysMemo(n - 1, memo) + waysMemo(n - 2, memo);  memo.set(n, answer);  return answer;}function waysTab(n) {                        // bottom-up, O(1) space  let prev = 1, curr = 1;                    // ways(0) and ways(1)  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];  return curr;}console.log(waysMemo(5), waysTab(5));   // 8 8console.log(waysMemo(10), waysTab(10)); // 89 89

Min cost climbing stairs gives each stair a price and asks for the cheapest route. The state is the step we are standing on. The transition picks the cheaper of the two ways to arrive. Here optimal substructure does real work: the cheapest route to step i must contain a cheapest route to the step it came from.

// Min cost climbing stairs: cost[i] is paid when you step OFF stair i (1 or 2 steps up).// Start on stair 0 or 1 for free; the goal is "one past the last stair", index n.function minCostClimbingStairs(cost) {  const n = cost.length;  const dp = new Array(n + 1).fill(0);       // dp[i] = cheapest way to be standing on step i  for (let i = 2; i <= n; i++) {    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);  }  return dp[n];}console.log(minCostClimbingStairs([10, 15, 20]));                        // 15console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])); // 6

When greedy fails, DP still works

Lesson 47 ended with an example where greedy fails. The coins are 1, 3 and 4, and the amount is 6. The greedy rule “take the biggest coin that fits” gives 4 + 1 + 1 (three coins). But 3 + 3 needs only two coins. Greedy picks one choice and never goes back. DP instead tries every possible last coin and trusts the best answer it already worked out for the rest.

// Fewest coins for an amount. Lesson 47: greedy (biggest coin first) can be wrong.function greedyCoins(coins, amount) {  const sorted = [...coins].sort((a, b) => b - a);  let count = 0;  for (const c of sorted) {    count += Math.floor(amount / c);    amount %= c;  }  return amount === 0 ? count : -1;}// DP: dp[a] = fewest coins that add up to exactly a.function dpCoins(coins, amount) {  const dp = new Array(amount + 1).fill(Infinity);  dp[0] = 0;                                 // zero coins make amount 0  for (let a = 1; a <= amount; a++) {    for (const c of coins) {      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);   // try c as the last coin    }  }  return dp[amount] === Infinity ? -1 : dp[amount];}console.log(greedyCoins([1, 3, 4], 6)); // 3   (4 + 1 + 1)console.log(dpCoins([1, 3, 4], 6));     // 2   (3 + 3)

Practice questions

For each question, first write the state, the transition and the base cases. Then code the plain recursion, add the cache, and try to make it smaller.

function fib(n) {  if (n <= 1) return n;  return fib(n - 1) + fib(n - 2);}console.log(fib(2)); // 1console.log(fib(4)); // 3console.log(fib(0)); // 0

function fib(n, memo = new Map()) {  if (n <= 1) return n;  if (memo.has(n)) return memo.get(n);  const answer = fib(n - 1, memo) + fib(n - 2, memo);  memo.set(n, answer);  return answer;}console.log(fib(2));  // 1console.log(fib(4));  // 3console.log(fib(30)); // 832040

function fib(n) {  if (n <= 1) return n;  let prev = 0, curr = 1;  for (let i = 2; i <= n; i++) {    [prev, curr] = [curr, prev + curr];  }  return curr;}console.log(fib(2));  // 1console.log(fib(4));  // 3console.log(fib(0));  // 0console.log(fib(30)); // 832040

function climbStairs(n) {  if (n <= 1) return 1;  return climbStairs(n - 1) + climbStairs(n - 2);}console.log(climbStairs(2)); // 2console.log(climbStairs(3)); // 3console.log(climbStairs(5)); // 8

function climbStairs(n, memo = new Map()) {  if (n <= 1) return 1;  if (memo.has(n)) return memo.get(n);  const answer = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);  memo.set(n, answer);  return answer;}console.log(climbStairs(2));  // 2console.log(climbStairs(3));  // 3console.log(climbStairs(5));  // 8console.log(climbStairs(45)); // 1836311903

function climbStairs(n) {  let prev = 1, curr = 1;                    // ways(0) and ways(1)  for (let i = 2; i <= n; i++) {    [prev, curr] = [curr, prev + curr];  }  return curr;}console.log(climbStairs(2));  // 2console.log(climbStairs(3));  // 3console.log(climbStairs(5));  // 8console.log(climbStairs(45)); // 1836311903

function minCostClimbingStairs(cost) {  const memo = new Map();  function best(i) {    if (i <= 1) return 0;                    // starting on stair 0 or 1 is free    if (memo.has(i)) return memo.get(i);    const answer = Math.min(best(i - 1) + cost[i - 1], best(i - 2) + cost[i - 2]);    memo.set(i, answer);    return answer;  }  return best(cost.length);}console.log(minCostClimbingStairs([10, 15, 20]));                         // 15console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])); // 6

function minCostClimbingStairs(cost) {  let twoBack = 0, oneBack = 0;              // dp[i-2] and dp[i-1], starting at i = 2  for (let i = 2; i <= cost.length; i++) {    const here = Math.min(oneBack + cost[i - 1], twoBack + cost[i - 2]);    twoBack = oneBack;    oneBack = here;  }  return oneBack;}console.log(minCostClimbingStairs([10, 15, 20]));                         // 15console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])); // 6

function tribonacci(n, memo = new Map()) {  if (n === 0) return 0;  if (n <= 2) return 1;  if (memo.has(n)) return memo.get(n);  const answer = tribonacci(n - 1, memo) + tribonacci(n - 2, memo) + tribonacci(n - 3, memo);  memo.set(n, answer);  return answer;}console.log(tribonacci(4));  // 4console.log(tribonacci(25)); // 1389537

function tribonacci(n) {  if (n === 0) return 0;  if (n <= 2) return 1;  let a = 0, b = 1, c = 1;                   // T(i-3), T(i-2), T(i-1)  for (let i = 3; i <= n; i++) {    [a, b, c] = [b, c, a + b + c];  }  return c;}console.log(tribonacci(4));  // 4console.log(tribonacci(25)); // 1389537console.log(tribonacci(0));  // 0

function rob(nums) {  const memo = new Map();  function best(i) {                         // most money from houses 0..i    if (i < 0) return 0;    if (memo.has(i)) return memo.get(i);    const answer = Math.max(best(i - 1), nums[i] + best(i - 2));    memo.set(i, answer);    return answer;  }  return best(nums.length - 1);}console.log(rob([1, 2, 3, 1]));    // 4console.log(rob([2, 7, 9, 3, 1])); // 12

function rob(nums) {  let twoBack = 0, oneBack = 0;              // best(i-2) and best(i-1)  for (const money of nums) {    const here = Math.max(oneBack, twoBack + money);    twoBack = oneBack;    oneBack = here;  }  return oneBack;}console.log(rob([1, 2, 3, 1]));    // 4console.log(rob([2, 7, 9, 3, 1])); // 12console.log(rob([5]));             // 5

function generate(numRows) {  const triangle = [[1]];  for (let r = 1; r < numRows; r++) {    const prev = triangle[r - 1];    const row = [1];    for (let j = 1; j < r; j++) row.push(prev[j - 1] + prev[j]);    row.push(1);    triangle.push(row);  }  return triangle;}console.log(generate(5)); // [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]console.log(generate(1)); // [[1]]

function generate(numRows) {  const memo = new Map();  function cell(r, c) {    if (c === 0 || c === r) return 1;    const key = r + "," + c;    if (memo.has(key)) return memo.get(key);    const value = cell(r - 1, c - 1) + cell(r - 1, c);    memo.set(key, value);    return value;  }  const triangle = [];  for (let r = 0; r < numRows; r++) {    const row = [];    for (let c = 0; c <= r; c++) row.push(cell(r, c));    triangle.push(row);  }  return triangle;}console.log(generate(5)); // [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]console.log(generate(1)); // [[1]]

function getRow(rowIndex) {  let prev = [1];  const all = [prev];  for (let r = 1; r <= rowIndex; r++) {    const row = [1];    for (let j = 1; j < r; j++) row.push(prev[j - 1] + prev[j]);    row.push(1);    all.push(row);    prev = row;  }  return all[rowIndex];}console.log(getRow(3)); // [ 1, 3, 3, 1 ]console.log(getRow(0)); // [ 1 ]console.log(getRow(1)); // [ 1, 1 ]

function getRow(rowIndex) {  const row = [1];  for (let r = 1; r <= rowIndex; r++) {    row.push(1);                             // the new row is one longer    for (let j = r - 1; j >= 1; j--) {      row[j] += row[j - 1];                  // right to left: row[j-1] is still the old value    }  }  return row;}console.log(getRow(3)); // [ 1, 3, 3, 1 ]console.log(getRow(0)); // [ 1 ]console.log(getRow(1)); // [ 1, 1 ]

Make it stick

What's next

In Lesson 55 you will practise this recipe on classic 1-D problems: house robber (take or skip), coin change, decode ways, word break and the longest increasing subsequence. In each one, the main work is choosing the state and the transition.