Dynamic programming

The two conditions

Dynamic programming is not a technique so much as a diagnosis. It applies when a problem has both of these, and when it does, the fix is almost mechanical:

• Overlapping subproblems — the same smaller question comes up again and again. fib(30) asks for fib(10) about 832 000 times.
• Optimal substructure — the best answer is built from the best answers to the smaller versions. The cheapest route through a grid ends with the cheapest route to one of the two cells before it.

Without overlap, caching buys nothing — that is plain divide and conquer, like merge sort. Without optimal substructure, the small answers cannot be combined and you need a search instead.

Top down: memoise

Four lines around the original recursion, and the complexity collapses from O(2ⁿ) to O(n). That is the whole of top-down DP, and it is the form to reach for first: the recursion already describes the problem, so you have only to stop it repeating itself.

Its advantages are that it computes only the subproblems actually needed, and that it is hard to get wrong. Its cost is the call stack, and a deep problem can overflow it.

/* exponential: 2.7 million calls for n = 32 */
const fib = (n) => (n < 2 ? n : fib(n - 1) + fib(n - 2));

/* linear: 33 calls, and the recursion is unchanged */
function memoFib() {
  const cache = new Map();

  const go = (n) => {
    if (n < 2) return n;
    if (cache.has(n)) return cache.get(n);

    const value = go(n - 1) + go(n - 2);
    cache.set(n, value);

    return value;
  };

  return go;
}

Bottom up: tabulate

Same answers, no recursion, no stack — and once the table exists you can usually see that most of it is never read again, which turns O(n) memory into O(1). That rolling-window reduction is the second half of most DP solutions and the part that makes them practical on real sizes.

function fib(n) {
  const table = [0, 1];
  for (let i = 2; i <= n; i++) table[i] = table[i - 1] + table[i - 2];
  return table[n];
}

/* and since only the last two matter, the table is not needed at all */
function fib(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

A two-dimensional one

Every cell asks one question: what is the cheapest way to turn the first i characters of a into the first j of b? Each answer is built from three neighbours already computed. O(a × b) time and O(a × b) memory — and since each row only needs the row above it, O(min(a, b)) memory if you want it.

This is what a spell checker, a diff tool and git itself are doing.

function editDistance(a, b) {
  const rows = a.length + 1;
  const cols = b.length + 1;
  const d = Array.from({ length: rows }, () => new Array(cols).fill(0));

  for (let i = 0; i < rows; i++) d[i][0] = i;      // delete every character
  for (let j = 0; j < cols; j++) d[0][j] = j;      // insert every character

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      d[i][j] = a[i - 1] === b[j - 1]
        ? d[i - 1][j - 1]                          // the characters match: free
        : 1 + Math.min(d[i - 1][j - 1],            // substitute
                       d[i - 1][j],                // delete
                       d[i][j - 1]);               // insert
    }
  }

  return d[rows - 1][cols - 1];
}

How to find the recurrence

The classic problems are all this shape: coin change, knapsack, longest common subsequence, edit distance, grid paths, stair climbing, word break. They look different and they are the same five steps.

• Name the state. What does one subproblem look like? "The best I can do using the first i items with capacity c." Getting this right is most of the work.
• Write the choice. At each state, what are the options? Usually: take this item, or skip it.
• Write the base case. The smallest state you can answer without thinking.
• Memoise first, tabulate second. Get it correct as a recursion, then convert if you need the speed or the stack.
• Then shrink the memory. Look at which rows of the table are still read. It is usually one or two.