Dynamic programming step by step: deriving edit distance

Goal

Solve a problem whose optimal answer is built from optimal answers to smaller instances, and whose naive recursion recomputes the same instances exponentially often, in polynomial time and predictable memory.

Prerequisites

Two properties: optimal substructure (the best solution contains best solutions to subproblems) and overlapping subproblems (the number of distinct subproblems is polynomial while the naive call tree is not). The example: the edit distance between strings a (length m) and b (length n), the minimum number of single-character insertions, deletions and substitutions turning a into b.

Steps

1. Define the state as the smallest set of parameters that identifies a subproblem: D(i, j) is the edit distance between the first i characters of a and the first j characters of b. The answer is D(m, n).
2. Write the base cases: D(i, 0) = i (delete everything) and D(0, j) = j (insert everything).
3. Write the recurrence. If a[i-1] == b[j-1], then D(i, j) = D(i-1, j-1). Otherwise D(i, j) = 1 + min(D(i-1, j), D(i, j-1), D(i-1, j-1)), the three terms being deletion, insertion and substitution.
4. Count the states: (m+1) * (n+1), each computed in constant time from three neighbours, so the algorithm is O(mn). Naive recursion revisits D(i-1, j-1) from three callers and explodes.
5. Memoise top-down: write the recurrence literally as a recursive function and decorate it with @functools.cache (documented in functools next to lru_cache). This is the fastest way to get a correct version, but depth grows with m + n, so it suits short inputs.
6. Tabulate bottom-up: fill a table row by row, because each cell needs only the row above and the cell to its left. For kitten and sitting the table ends with D(6, 7) = 3: substitute k with s, substitute e with i, insert g.
7. Cut memory: keep only the previous and the current row, giving O(min(m, n)) space. Keep the full table when the actual edit script is needed and backtrack from D(m, n).
8. Verify against brute force on small random strings, plus empty strings, identical strings and one-character differences.

Expected result

A function with quadratic time and linear space whose recurrence is written in a comment next to the code, checked against a brute-force oracle.

Limits and test basis

Problems without optimal substructure (longest simple path in a graph) do not yield to this method. State spaces over subsets are exponential in the set size and only feasible for small inputs. The figures for the example follow from the recurrence by arithmetic; no timings are claimed.