Dynamic Programming & Optimization

Edit Distance

The fewest insert/delete/substitute edits to turn one string into another — built up from a grid of subproblems.

Cell (i, j) = the edit distance of A's first i letters and B's first j. Each fills from three neighbors (orange); the blue box is the current cell; the green trail is one optimal alignment.

What you're seeing

To measure how different two strings are, we count the minimum number of single-character edits — insert, delete, or substitute — to turn one into the other. The trick is to solve every prefix pair first. Cell (i, j) holds the distance between A's first i letters and B's first j, and it depends only on three already-solved neighbors: the cell diagonally up-left (substitute or, if the letters match, a free keep), directly up (delete from A), and directly left (insert into B). Fill the grid row by row and the bottom-right corner is the answer; the green trail back to the top-left reads off one optimal sequence of edits.

The rule

dp[0][j] = j     # "" → B[0..j): j inserts
dp[i][0] = i     # A[0..i) → "": i deletes
dp[i][j] = (A[i-1] == B[j-1])
           ? dp[i-1][j-1]                              # free match
           : 1 + min( dp[i-1][j-1],   # substitute
                      dp[i-1][j],     # delete
                      dp[i][j-1] )    # insert

The invariant

The table is correct because each cell exactly answers its subproblem: dp[i][j] is the true minimum edit distance between A[0..i) and B[0..j). It holds for the base row and column (turning a string into the empty string costs one edit per character), and the recurrence preserves it: any way to align the two prefixes must end in one of three moves — match/substitute the last characters, delete A's last, or insert B's last — and each move's cost is a ±1 on a strictly smaller, already-correct subproblem. Taking the minimum over the three is therefore the true optimum for (i, j). This is dynamic programming's signature: optimal substructure (the best solution is built from best sub-solutions) plus overlapping subproblems (each cell is reused by the three cells below-and-right of it), so a Θ(m·n) table replaces exponential recursion.

The cost

DP tableNaive recursion TimeΘ(m·n)exponential SpaceΘ(m·n)—

Filling each of the (m+1)(n+1) cells in O(1) gives Θ(m·n) — versus the exponential blow-up of recomputing the same prefix pairs over and over. If you only need the distance (not the alignment), each row depends only on the previous one, so space drops to Θ(min(m, n)). Recovering the actual alignment needs the full table (or Hirschberg's clever Θ(m·n)-time, Θ(min(m,n))-space divide-and-conquer).

In the wild

Edit distance is the math behind spell-checkers and "did you mean…?", fuzzy search and record deduplication, diff and version-control merge (the closely related longest-common-subsequence), and — most heavily — bioinformatics, where Needleman–Wunsch (global) and Smith–Waterman (local) sequence alignment are edit distance with biology-flavored scoring. It's the textbook gateway to dynamic programming, and its grid is the same shape you'll see in LCS, sequence alignment, and many other DP problems.

Try this

Step through a few cells and watch each one pick the cheapest of its three orange neighbors — a free diagonal when the row/column letters match, otherwise one plus the best neighbor. Then follow the green path: diagonal steps are keeps or substitutions, vertical steps delete, horizontal steps insert — that's the actual edit script.

References

  1. Wagner, R. A. & Fischer, M. J. "The String-to-String Correction Problem." Journal of the ACM 21(1):168–173, 1974. The DP algorithm.
  2. Levenshtein, V. I. "Binary codes capable of correcting deletions, insertions, and reversals." Soviet Physics Doklady 10(8):707–710, 1966.
  3. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §14 (Dynamic Programming) — incl. LCS. MIT Press, 2022.
  4. Needleman, S. & Wunsch, C. (1970); Smith, T. & Waterman, M. (1981) — sequence alignment.