The film
About 4:15, hosted by Rerun. It asks you one question and waits for your answer before it shows you. The guide's voice is not recorded yet, so for now the film plays with captions; the full words are also below.
Nothing loads until you press play.
The lab: the tide table
Type two strings and fill the table square by square, then trace the edits back from the corner; or try every way, with every call counted, for strings short enough to finish. In the film, kitten and sitting took 29,737 calls the slow way and 56 squares in the table; at 13 characters, 2,114,900,428 calls against 196 squares.
Everything is computed on your computer, in this page. Nothing is sent anywhere.
Everything the film says
Dynamic programming
Dynamic programming: remember what you already worked out.
Some problems are made of smaller problems that keep coming back. Tonight Rerun learns to solve each one once and write the answer down.
How different are two words
How different are two words? Count the fewest single-letter edits that turn one into the other: put a letter in, take one out, or change one.
Kitten becomes sitting in 3: change the k to an s, the e to an i, and add a g. This count is called the edit distance.
Try every way
The obvious way is to try everything. Look at the last letters: either delete one, insert one, or match or change them, and work out the rest of each case the same way.
That works, but the same smaller questions come up again and again. For kitten and sitting, the recursion made 29,737 calls. For intention and execution, 2,193,844.
Two phrases of thirteen characters. How many calls does trying every way make? (the film pauses here)
Too many calls
For two phrases of 13 characters, it made 2,114,900,428 calls and took 11,327 milliseconds on this computer. Each extra letter multiplies the work by about five and a half, and the factor keeps rising.
Yet there are only 196 different questions in the whole problem, the big one included. The rest is repetition.
The tide table
So write each answer down once, in a table: one row for each letter of the first word plus one for the empty start, and the same for the columns.
Each square needs only three others: the one above, the one to its left, and the one diagonally above and left. Fill them in order and the bottom corner is the answer. For kitten and sitting, 56 squares instead of 29,737 calls.
Robert Wagner and Michael Fischer published this table for strings in 1974, and others found it independently.
Reading the way back
The table also says which edits to make. From the bottom corner, step back to whichever neighbour gave its value, and each step is one edit or one match.
Halve the beach and half the beach are 2 apart: drop the v, and change the e to an f.
A shortcut that fails
Why not just walk along both strings and fix each difference as you meet it? We tried that. It got both classic word pairs right.
It was wrong on all 6 of our guide sentences, and too high on 576 of 1,000 random pairs. A test with only the textbook examples would have passed it.
The idea
Richard Bellman chose the name dynamic programming around 1950, for problems solved in stages. Today it means: when a big problem is built from smaller ones that overlap, solve each smaller one once and keep the answer.
The same idea finds shortest routes and decodes speech.
Goodnight
When the same question keeps coming back, write the answer down.
Goodnight.
Sources
Every claim in the film, with where it comes from and what that source does not prove. The numbers about the model are computed from its weights, which you can load and check: facts.json.
Night School's edit-distance measurements. media/school/editdistance/facts.json, written by tools/school/fill_editdistance.mjs from system/school/editdistance.mjs: the table, the naive and memoised recursions with call counters, a breadth-first check, and a greedy control. https://github.com/HarperZ9/HarperZ9.github.io/tree/main/media/school/editdistance
Used for: Every distance, call count and cell count in the film, and the greedy control.
Does not prove: Costs under other edit weights.
Wagner and Fischer, The string-to-string correction problem (1974). Robert A. Wagner and Michael J. Fischer, J. ACM 21(1):168-173, 1974. https://doi.org/10.1145/321796.321811
Used for: The dynamic-programming table for edit distance.
Does not prove: The film's counts.
Dreyfus, Richard Bellman on the birth of dynamic programming (2002). Stuart Dreyfus, Operations Research 50(1):48-51, 2002, quoting Bellman, Eye of the Hurricane (1984). https://ideas.repec.org/a/inm/oropre/v50y2002i1p48-51.html
Used for: Bellman chose the name around 1950 at RAND, for multistage decision processes.
Does not prove: The modern overlapping-subproblems wording, which is the later textbook framing.
Bellman, Dynamic Programming (1957). Richard Bellman, Dynamic Programming, Princeton University Press, 1957.
Used for: The name and the general idea of dynamic programming.
Does not prove: Any claim about edit distance.
Jurafsky and Martin, Speech and Language Processing, section 2.9 (draft). Daniel Jurafsky and James H. Martin, Speech and Language Processing, 3rd edition draft, section 2.9, Minimum Edit Distance. https://web.stanford.edu/~jurafsky/slp3/
Used for: intention and execution are 5 apart with unit costs; the table was named by Wagner and Fischer and found independently by many; dynamic programming also finds shortest paths, and the Viterbi algorithm for speech extends it.
Does not prove: The film's call counts.
What this lesson leaves out
Unit costs: inserting, deleting or changing a letter each costs 1.
Call counts for long strings come from the recursion's own formula, checked against the running counter up to 13 characters.
Wagner and Fischer's paper and Bellman's book were checked by their bibliographic records; the naming date comes from Dreyfus's 2002 account.
Before this: Search and sorting (A26).