Dynamic Programming

Here is the most useless-sounding advice in programming: if you compute the same thing twice, write it down the first time.

That is dynamic programming. The whole subject. Everything else is figuring out what “the same thing” means for your particular problem.

The waste, made visible

Fibonacci, written the way the definition reads:

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Correct. Now draw the calls for fib(5):

                    fib(5)
                  /        \
            fib(4)          fib(3)
           /      \        /      \
      fib(3)     fib(2)  fib(2)   fib(1)
      /    \     /   \    /   \
  fib(2) fib(1) …    …   …    …

fib(3) is computed twice. fib(2) three times. The duplication doubles at every level, so fib(40) makes over 300 million calls — to produce 40 numbers.

The fix is embarrassing:

function fib(n: number, memo = new Map<number, number>()): number {
  if (memo.has(n)) return memo.get(n)!;          // already worked this out
  if (n <= 1) return n;

  memo.set(n, fib(n - 1, memo) + fib(n - 2, memo));
  return memo.get(n)!;
}

300 million calls become 40. Exponential to linear, by adding a Map.

The two preconditions

Memoisation only helps when both of these hold, and it is worth being able to check them deliberately:

Overlapping subproblems. The same smaller question comes up more than once. Merge sort recurses just as hard, but its halves are all different — nothing to cache, which is why merge sort is not a DP problem.

Optimal substructure. The best answer is built from best answers to smaller versions. The shortest route through a town is the shortest route to that town plus the shortest route onward.

That second one fails more often than people expect. If your subproblem’s answer depends on how you arrived at it, you cannot cache by the subproblem alone — which is a signal that your state is missing something.

Building the table instead

Rather than recursing and caching, you can fill a table from the smallest case upward. Same computation, no call stack.

Here is the classic: count the paths from the top-left of a grid to the bottom-right, moving only right or down, with one square walled off.

Every cell is above + left, and each one is read later but computed once.

function countPaths(grid: boolean[][]): number {
  const [rows, cols] = [grid.length, grid[0]!.length];
  const table = Array.from({length: rows}, () => new Array<number>(cols).fill(0));

  for (let r = 0; r < rows; r += 1) {
    for (let c = 0; c < cols; c += 1) {
      if (grid[r]![c]) continue;                         // wall: stays 0
      if (r === 0 && c === 0) { table[r]![c] = 1; continue; }
      table[r]![c] = (r > 0 ? table[r - 1]![c]! : 0) + (c > 0 ? table[r]![c - 1]! : 0);
    }
  }
  return table[rows - 1]![cols - 1]!;
}

Top-down or bottom-up?

They compute the same thing. The differences are practical:

Write top-down first. It is much easier to get right, because the recursion is the recurrence and you cannot get the ordering wrong. Convert to a table only if you hit a stack limit or you need the memory trick.

Finding the state is the actual work

Everything above is mechanical. The part that takes thought is: what has to be in the cache key?

The rule: the state must capture everything about the past that affects the future. Nothing more.

Take the knapsack problem — items with weights and values, a bag with a capacity, maximise value. Trying f(i) = “best value using the first i items” fails, because whether item 5 fits depends on how much room you have used. That is past information the future depends on, and it is missing.

Add it: f(i, remaining) = “best value from items i onward with remaining capacity”. Now nothing else about the path taken matters.

function knapsack(items: {weight: number; value: number}[], capacity: number): number {
  const memo = new Map<string, number>();

  function best(i: number, remaining: number): number {
    if (i === items.length) return 0;
    const key = `${i},${remaining}`;
    if (memo.has(key)) return memo.get(key)!;

    const skip = best(i + 1, remaining);
    const take = items[i]!.weight <= remaining
      ? items[i]!.value + best(i + 1, remaining - items[i]!.weight)
      : -Infinity;                                  // does not fit

    memo.set(key, Math.max(skip, take));
    return memo.get(key)!;
  }

  return best(0, capacity);
}

Shrinking the table

Look at the grid code again: row r only ever reads row r - 1. Rows 0 through r - 2 are never touched again, so why keep them?

let previous = new Array<number>(cols).fill(0);
for (let r = 0; r < rows; r += 1) {
  const current = new Array<number>(cols).fill(0);
  // …fill current from previous and current…
  previous = current;
}

$O(rows \times cols)$ memory becomes $O(cols)$. Fibonacci gets the same treatment and collapses to two variables.

This only works bottom-up — recursion can jump to any state at any time, so nothing can be discarded.

The recurring shapes

Most DP problems are one of a handful of recurrences wearing a costume:

• Linear — f(i) depends on f(i-1), f(i-2). Fibonacci, climbing stairs, house robber.
• Two sequences — f(i, j) over positions in both. Edit distance, longest common subsequence, sequence alignment in bioinformatics.
• Interval — f(i, j) over a range, splitting at every k inside it. Matrix chain multiplication, burst balloons.
• Subset — the state is a bitmask of which items are used. Travelling salesman for small $n$.
• Digit — build a number one digit at a time, carrying “am I still tight against the bound”.

Recognising the shape tells you the state, and the state is the hard part. The rest, as promised, is writing things down.