Two Axes: Reading the Answer Back Out
When one index is not enough the table grows a second axis and nothing else changes. Grid routes, shared letters and edit distance, plus the traceback that turns a number into an actual answer.
One index stops being enough the moment a problem has two things to keep track of at once. Two strings, or a position on a grid, or a list of items together with a budget. The state grows a second component, the table grows a second axis, and everything else stays exactly where it was.
That's really the whole of the promotion. You still write a rule for one cell in terms of cells that are already filled, you still check that no arrow points forward, and you still fill in an order that respects them. Nothing new is being introduced here except a second subscript. Nothing else moves.
A grid you can walk across
Start with the case where the table looks like the problem, since it makes everything after it easier to believe. A grid of tolls, one number per square, and the only legal moves are right and down. Get from the top-left corner to the bottom-right for as little money as you can manage.
Two moves reach any square, and both of them come from squares up and to the left. However the cheapest route into a square arrived, it arrived either from above or from the left, so the cheapest way into a square is that square's own toll plus the cheaper of its two neighbors.
The edges are the fiddly part, and they're fiddly in a thoroughly boring way. The top row has nothing above it and the left column has nothing to its left, so each of those cells has exactly one way in and simply copies its single neighbor. The corner has no way in at all, so its cost is just given rather than computed, and then the loop takes over.
Set the widget below to Cheapest route and play it through. Watch the arrows while the table fills, then keep watching after it's full.
cheap(0,0) = grid(0,0) · cheap(r,c) = grid(r,c) + min(cheap(r - 1, c), cheap(r, c - 1))
across: column|down: row
Once the table is full, walking backwards from the corner turns a cost into an actual route. The table says what the trip costs; the walk back says which way to go.
The start costs 1 and there is no way in but to be there.
Reading the route back out
The corner cell says the trip costs 9. It doesn't say which way to go, and for most real uses the route is the thing you actually wanted.
The table has it anyway. Stand on the finishing square and ask which neighbor it read from, whichever of the two was cheaper. Step onto that one and ask the same question again. Keep going until you reach the start, and the squares you touched are the route, recovered backwards.
This is a general move rather than a trick for grids, and it's worth filing as one. A dynamic programming table records the value of every subproblem, so walking backwards through it and asking which choice produced each value reconstructs the decisions that were made. It's also the reason the memory trick from two tutorials ago isn't free: throw the table away and you keep the number while losing the answer.
Two strings, two axes
The grid was easy because the table looked like the input, and that won't happen again. The string problems are the same idea with the picture taken away, and they earn the extra effort several times over, since they turn up in spell-checkers, in file comparison, and in every version control system you've ever used. Diff is this algorithm.
Longest common subsequence. Given two strings, find the longest run of letters that appears in both in the same order, not necessarily next to each other. Cell (i, j) holds the answer for the first i letters of one string measured against the first j letters of the other.
The rule splits on a single comparison. If the two prefixes end in the same letter, pair those two letters up and add 1 to the answer for both prefixes one shorter, the diagonal neighbor. If they end in different letters, then at least one of those letters can't be used in the answer, so give up whichever loses less and take the better of the cell above and the cell to the left.
Row 0 and column 0 are all zeros. The reason is worth stating rather than asserting, since it's the base case doing exactly the job base cases always do: an empty prefix shares no letters with anything.
Edit distance. The same table with a different question written on it. Count the fewest single-letter edits that turn one string into the other, where an edit means inserting a letter, deleting one, or substituting one for another.
Three neighbors this time, and each of the three is one of the edits. The cell above is a deletion, the cell to the left is an insertion, and the diagonal is a substitution. Take the cheapest of the three and add one for the edit you just made. The exception is the case that costs nothing: when both prefixes end in the same letter, that letter's already correct, and the cell copies its diagonal neighbor untouched. Matches are free.
The base cases say the same thing twice from opposite ends. Turning nothing into a string of length j takes j insertions, and turning a string of length i into nothing takes i deletions. Those two fill the first row and the first column before the loop starts.
Turning kitten into sitting costs three edits. That's what the table lands on, and it's also what you get doing it by hand: substitute the k for an s, substitute the e for an i, and add a g on the end.
Both string problems live in the same widget. Switch to Shared letters or to Edit distance and step through them, paying attention to how the arrows change between a match and a mismatch. A match reads one cell. A mismatch reads two or three.
lcs(r,0) = lcs(0,c) = 0 · if the letters match: lcs(r,c) = 1 + lcs(r - 1, c - 1) · if they differ: lcs(r,c) = max(lcs(r - 1, c), lcs(r, c - 1))
across: BDCAB|down: ABCB
A match steps diagonally and adds one. A mismatch has to give up one letter or the other, so it copies the better neighbor.
One of the two prefixes is empty, so there is nothing to share. Zero.
The shape of the cost
Costing a two-dimensional solution is the same multiplication as before. Cells are states, each cell does a fixed amount of work, so a table of m by n cells costs m times n and nothing more.
Two strings of length 1000 make a million cells, which any computer fills without noticing. Two strings of length a million make a trillion cells, which it doesn't. That quadratic cost is the real ceiling on these algorithms, and the specialized versions used in production exist almost entirely to dodge it.
In an edit distance table, what does the cell directly above represent?
1/3Both string problems use one table and differ only in what a cell means and which neighbors it reads. That pattern is worth trusting, because it keeps holding. The last tutorial in this section puts it on a problem where the second axis isn't a sequence at all.