Do not re-solve what you have already solved. Bellman's method breaks a hard optimization into overlapping sub-problems, solves each once, and stores the answer — the principle of optimality. Here it is runnable: the least-cost way to turn one word into another, built one table cell at a time as min(insert, delete, substitute). Down the center, data flows: two strings go in, the table fills, the edit distance and its alignment come out. The blue team builds and defends it; the red team tries to break it.
source Bellman, Dynamic Programming, Princeton University Press (1957) — archive.org/details/dynamicprogrammi0000bell. Rendered, not quoted.
Let D[i][j] be the cheapest way to turn the first i letters of A into the first j letters of B. It is built from three neighbours already solved:
D[i][j] = min( D[i−1][j] + 1 (delete A[i]), D[i][j−1] + 1 (insert B[j]), D[i−1][j−1] + c (match/substitute) ), where c = 0 if the letters agree, else 1.
Base cases: an empty string costs its counterpart's length. The answer is the bottom-right corner. Every cell is computed once — that is the whole saving. The live table, and the traced path, are in the panel.
Bellman (1957) named the load-bearing fact: an optimal solution is built from optimal solutions of its parts — the principle of optimality. Overlapping sub-problems + optimal substructure = solve-once, reuse.
That single shape recurs downstream: sequence alignment (Needleman–Wunsch) is this exact table with a scoring scheme; Viterbi is it over hidden states; reinforcement learning is it over time, where D becomes the value function. Each sphere is the next one's premise.
The blue team's live check: recompute the DP distance for a fixed battery of string pairs and confirm every one against a brute-force recursive oracle. If red tampers, the DP disagrees with the oracle and this badge goes red.
The input is a pair of strings, A (source) and B (target), over any alphabet. Three edit operations are allowed, each costing 1:
| op | does | move in table |
|---|---|---|
| insert | add a letter of B | from the left |
| delete | drop a letter of A | from above |
| substitute | swap A's letter for B's | diagonal (+1) |
| match | letters already agree | diagonal (+0) |
Edit the two strings below and the table refills. That is what you feed the panel — nothing else is assumed.
The table below fills live — highlighted cells are the traced optimal path; the green corner is the answer.
one optimal alignment:
Change either string — the distance is filled cell by cell from the recurrence on the spot, never looked up.
What the machine produces, proven: the minimum edit cost equal to a brute-force recursive oracle across the witness battery; the classic kitten → sitting = 3; every interior cell satisfying the recurrence; and a traced-back alignment whose cost equals the table's bottom-right value.
The blue team's witness (left) confirms these live; the red team (right) tries to make them wrong.
And DP is not free: the full table is O(nm) time and space. Hirschberg recovers the alignment in O(n) space; band/greedy methods trade optimality for speed. The traceback also returns just one optimal alignment — ties are silently broken. DP is the first proof the problem has a computable shape, not the last word on solving it.
"Dynamic programming is about computer programming." Cut. Bellman's "programming" means planning / tabular optimization, from operations research — the name predates the modern sense of code.
"Edit distance is always symmetric: d(A,B)=d(B,A)." Cut for the general case. True for unit costs (shown here), but false once insert and delete cost differently.
"Greedy letter-matching gives the minimum." Cut. Greedy fails; only the full recurrence over sub-problems is guaranteed optimal — which is exactly why DP exists.
The red team's move: drop the substitution from the recurrence, leaving only insert and delete, and try to pass off the inflated number as the true distance. The blue team's witness (window 7) is watching.
Without substitution, changing a letter costs a delete plus an insert — so kitten → sitting reads 5, not 3. The witness recomputes, disagrees with the oracle, and turns red. Nothing is faked; the attack is real and it is caught.