A First Taste of Algorithms · Recursion That Remembers

When the table method works — and the spell-checker

Two ingredients made all of this go, and they are worth naming because together they are a diagnostic you can run on new problems:

1. Optimal substructure: the best answer to the whole is assembled from best answers to subproblems. (The first hop of an optimal climb leaves an optimal climb; the first coin of an optimal payment leaves an optimal payment. The Diamond makes this precise — there is a cut-and-paste argument hiding in “leaves.”)
2. Overlapping subproblems: the recursion meets the same subproblem many times — otherwise the notebook records answers nobody asks for twice. Merge sort has perfect substructure and zero overlap (its two halves are different lists); memoizing it buys nothing. The notebook pays exactly where the tree repeats.

The diagnostic passes on a problem that runs, today, inside every phone you have ever typed on. How does a spell-checker know that when you typed “graet” you meant “great”? It measures the edit distance between words: the fewest one-letter edits — insert a letter, delete a letter, or replace a letter — turning one word into the other. Both questions of the book apply: a correct procedure, at what cost? — and the table method answers, because the problem has the grammar of the staircase. Look at the last letters of the two words. If they match, they cost nothing: the distance is whatever the rest costs. If they differ, your last edit was one of exactly three kinds — replace one with the other, delete one, or insert one — and each choice leaves a smaller two-word problem. Three branches, a min, a floor (the distance from any word to the empty word is its length: delete everything). Subproblems — “first part of word one versus first part of word two” — overlap massively, so the notebook is a two-dimensional table, one row per prefix of the first word, one column per prefix of the second.

Small enough to do at a desk: “cap” to “tape” has distance 2 (replace c→t, then insert the e), and the 4 × 5 table verifying it is Fluency 1.5. Big enough to matter: the same table, grown, compares DNA sequences, suggests your search-bar corrections, and shows lawyers what changed between contract drafts. One grammar — last decision, three branches, min, floor, notebook — and you should feel the chapter consolidating into a method you could point at a problem neither of us has seen.

Deeper water: the craft is the state

The table method’s honest limitation: ingredient 1 can fail, and when it fails it fails quietly. Try planning the best two-week trip as “the best first week, then the best second week from wherever it ended” — and watch the assembly break: the two weeks interact (one budget, one energy, can’t see the same city twice), so the best whole is not built from the best parts. Subproblems that share a resource are not really sub-problems; they are one coupled problem wearing two name tags.

The professional response is not to abandon the method but to enrich the state: don’t tabulate best(week), tabulate best(week, money remaining) — fold the shared resource into the question itself, and substructure is restored, at the price of a bigger table. Choosing what the table’s questions are — the state — is the actual craft of dynamic programming; the recurrences write themselves once the state is right. The staircase’s state was one number; the coins’, one number; edit distance needed two. Problem 3.4 hands you a coupled problem and asks you to design the state that uncouples it. And a forward pointer: in Chapter 9, a famous algorithm will silently memoize shared subexpressions in the chain rule — the notebook idea, working inside calculus — so file this chapter somewhere permanent.

Where this leaves us

The exponential wall, it turns out, comes in two materials. Hanoi’s was stone — every move proved necessary. The staircase’s was paper: few questions, asked absurdly often, and one notebook tore it down. Dynamic programming is the systematic tearing: find the grammar (last decision, few branches, min or sum, floor), name the state, fill the table — top-down with a memo or bottom-up with a loop, same table either way. Greedy commits before pricing; the table prices before committing; Sevenia’s 14 costs two coins forever now, and you can prove it.

The tables themselves are trying to tell you something, if you look at them sideways. Entry 14 depended on entries 13, 7, and 4; those depended on others; the whole computation is a web of questions pointing at the questions they need — dots and arrows, a territory with a map. Chapter 5 stops solving problems long enough to study the maps themselves: things connected to things, the shape behind staircases, subway lines, friendships, and the web — and the two or three ways of walking such a territory that answer almost every question about it.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses