Dynamic programming

Why you need this

A hidden Markov model over 300 columns with 6 section types has $6^{300}$ possible hidden paths. The forward algorithm adds up the probability of every one of them, and Viterbi finds the best one, each in about $300 \times 36$ operations. The trick is dynamic programming: all those paths share prefixes, so compute each prefix's answer once, store it in a table, and build each column from the one before it.

The idea

Overlapping subproblems

Some problems break into smaller copies of themselves, and the same small copies come up again and again. The Fibonacci numbers are the classic case: $F(n) = F(n-1) + F(n-2)$. Plain recursion for $F(30)$ asks for $F(28)$ twice, $F(27)$ three times, and so on, over a million calls in total. Store each $F(k)$ the first time you compute it and the whole thing takes 30 additions. Dynamic programming is the name for "solve each subproblem once, remember the answer, build up".

Memoization versus tabulation

There are two ways to remember.

• Memoization is top-down. Write the recursive function as you naturally would, and keep a cache keyed by the argument. On entry, if the cache has the answer, return it; otherwise compute, store, return.
• Tabulation is bottom-up. Work out the order in which subproblems are needed, smallest first, allocate an array, and fill it in that order with a loop. No recursion.

Both give the same answers with the same big-O. Tabulation has no recursion depth to blow, makes the memory visible, and lets you throw away old columns when only the latest one is needed. This cluster uses tabulation everywhere.

Fill a table one column at a time

For sequence problems the table has one column per time step $t$ and one row per state $j$. Cell $(t, j)$ answers a question about everything that ends in state $j$ at step $t$. The key property: cell $(t, j)$ depends only on cells in column $t - 1$. So you fill column 1, then column 2 from column 1, and so on to column $T$.

Two flavors share this shape:

Pattern	Cell $(t, j)$ equals	Answers
SUM	sum over predecessors $i$ of (cell $(t-1, i)$ times the weight of stepping $i \to j$)	how many ways, or total probability
MAX	max (or min) over predecessors $i$ of (cell $(t-1, i)$ plus the cost of stepping $i \to j$), and remember which $i$ won	the best single path

The forward algorithm is the SUM pattern. Viterbi is the MAX pattern. Same table, same loop, one operator swapped, plus an array of backpointers in the MAX case so the winning path can be read back at the end.

Worked example

(a) Counting monotone paths on a grid

Take a 3 by 3 grid of points with $(x, y)$ from $(0, 0)$ at the top left to $(2, 2)$ at the bottom right, $x$ increasing to the right and $y$ downward. Moves go right or down only. How many paths reach the bottom-right corner?

Every path into a point arrives from the point above or the point to its left. So

$$\text{paths}(x, y) = \text{paths}(x - 1, y) + \text{paths}(x, y - 1)$$

with $\text{paths} = 1$ along the top row and left column, where there is only one way to go. Fill row by row:

	$x = 0$	$x = 1$	$x = 2$
$y = 0$	1	1	1
$y = 1$	1	2	3
$y = 2$	1	3	6

Six paths. Check by brute force: a path is a string of four moves with two R and two D, and there are six such strings. The table did 9 additions; brute force tested 16 strings. On a 20 by 20 grid the table does 400 additions while brute force faces about $10^{11}$ strings.

This is the SUM pattern with every step weighing 1. Put a probability on each step instead and you have the forward algorithm.

(b) Cheapest path down a grid of costs

Now a grid of costs, 3 rows tall and 4 columns wide. You may start in any cell of the top row and must end in the bottom row. Each step moves down one row to the cell directly below or to either diagonal neighbor, staying inside the grid. Find the path with the smallest total cost.

Costs:

	$x = 0$	$x = 1$	$x = 2$	$x = 3$
$y = 0$	3	1	4	2
$y = 1$	5	9	2	6
$y = 2$	5	3	5	8

Let $D(x, y)$ be the cheapest total of any valid path from the top row that ends at $(x, y)$. The top row is its own cost. Below that,

$$D(x, y) = \text{cost}(x, y) + \min\big(D(x-1, y-1),\; D(x, y-1),\; D(x+1, y-1)\big)$$

skipping any predecessor outside the grid, and recording which predecessor gave the minimum.

Row $y = 1$: $D(0,1) = 5 + \min(3, 1) = 6$ from $x = 1$; $D(1,1) = 9 + \min(3, 1, 4) = 10$ from $x = 1$; $D(2,1) = 2 + \min(1, 4, 2) = 3$ from $x = 1$; $D(3,1) = 6 + \min(4, 2) = 8$ from $x = 3$.

Row $y = 2$: $D(0,2) = 5 + \min(6, 10) = 11$ from $x = 0$; $D(1,2) = 3 + \min(6, 10, 3) = 6$ from $x = 2$; $D(2,2) = 5 + \min(10, 3, 8) = 8$ from $x = 2$; $D(3,2) = 8 + \min(3, 8) = 11$ from $x = 2$.

Table of $D$ with backpointers in parentheses:

	$x = 0$	$x = 1$	$x = 2$	$x = 3$
$y = 0$	3	1	4	2
$y = 1$	6 (from 1)	10 (from 1)	3 (from 1)	8 (from 3)
$y = 2$	11 (from 0)	6 (from 2)	8 (from 2)	11 (from 2)

The cheapest bottom cell is $D(1, 2) = 6$. Follow the backpointers upward: $(1, 2)$ came from $x = 2$, so $(2, 1)$; that came from $x = 1$, so $(1, 0)$. The path is $(1, 0) \to (2, 1) \to (1, 2)$ with costs $1 + 2 + 3 = 6$. Without backpointers you would know the best total but not the route.

function cheapestPathDown(cost) {
  const H = cost.length, W = cost[0].length;
  const D = cost.map(row => row.slice());           // row 0 of D is just row 0 of cost
  const back = cost.map(row => row.map(() => -1));
  for (let y = 1; y < H; y++)
    for (let x = 0; x < W; x++) {
      let best = Infinity, from = -1;
      for (const px of [x - 1, x, x + 1])
        if (px >= 0 && px < W && D[y - 1][px] < best) { best = D[y - 1][px]; from = px; }
      D[y][x] = cost[y][x] + best;
      back[y][x] = from;
    }
  let x = D[H - 1].indexOf(Math.min(...D[H - 1]));  // best end cell
  const path = [];
  for (let y = H - 1; y >= 0; y--) { path.unshift([x, y]); x = back[y][x]; }
  return { total: Math.min(...D[H - 1]), path };
}
console.log(cheapestPathDown([[3, 1, 4, 2], [5, 9, 2, 6], [5, 3, 5, 8]]));
// { total: 6, path: [ [ 1, 0 ], [ 2, 1 ], [ 1, 2 ] ] }

To turn this into Viterbi: rows become time steps $t$, columns become hidden states $j$, the cell cost becomes $-\log B_{j, O_t}$ (how unlikely state $j$ is to emit the tile seen at $t$), and each step from $i$ to $j$ adds $-\log A_{ij}$ instead of the zero-or-forbidden rule used here. The table is $\delta_t(j)$, the best log-probability of any path ending in state $j$ at time $t$, and the backpointers recover the hidden section sequence.

In a map generator

• Layout. The forward algorithm is the SUM pattern and tells you how probable a column sequence is. The Viterbi algorithm is the MAX pattern and recovers the section types behind a sequence of tiles. Baum-Welch runs the SUM pattern forward and backward and uses both tables.
• Fill. Checking that a generated cave is traversable is a reachability sweep, the same table with OR as the combining operator. Carving the cheapest corridor between two rooms through a cost field is example (b) on a bigger grid.
• Export. A "guaranteed completable" flag on a side-scroller level comes from a column-by-column reachable-set table: which heights can the player occupy at column $t$, given the heights reachable at $t - 1$.

Common mistakes

• Wrong fill order. Reading a cell before it is written. Symptom: zeros or undefined in the table, and results that change when you swap two loops.
• No backpointers. Trying to rebuild the path from the values alone. Symptom: the reconstructed path's total does not equal the table's best value.
• Wrong memory choice. Keeping the whole table when only the previous column is needed wastes memory; throwing it away when backpointers are needed loses the path. Symptom: out-of-memory on long sequences, or a correct score with no route.
• Mixing SUM and MAX. Using max inside the forward algorithm gives the probability of the single best path, not the total. Symptom: likelihoods too small, and Baum-Welch fails to converge.
• Tie-breaking by accident. < versus <= picks a different predecessor on ties. Symptom: two implementations agree on every total and disagree on the paths.
• Edges. Forgetting to skip out-of-range predecessors. Symptom: paths that hug or avoid the grid border for no reason, or an index error at $x = 0$.

Cost

For a sequence of length $T$ with $N$ states, where each cell looks at all $N$ predecessors, time is $O(T N^2)$. Memory is $O(T N)$ for the full table, which Viterbi needs for its backpointers, and $O(N)$ if only the final value matters. Example (b) on a $W \times H$ grid with $k$ allowed predecessors per cell is $O(W H k)$. Brute force over paths is $O(N^T)$: with $N = 6$ and $T = 300$ the table does about 10,800 operations against a number with 233 digits. It starts to hurt when $N$ climbs into the hundreds, since $N^2$ per column dominates, and when a fitting loop runs the whole thing thousands of times.

Going further

• Forward algorithm for SUM, Viterbi algorithm for MAX, Baum-Welch for both.
• Logarithms and underflow: why the MAX version adds costs instead of multiplying probabilities.
• Graphs and grids: Dijkstra's algorithm as dynamic programming on a graph with no fixed column order.
• Edit distance and the knapsack problem, two classic exercises with the same table shape.