Edit Distance — 2D DP on a grid

Turn "horse" into "ros" using the fewest single-character edits — insert, delete, or substitute. Answer: 3. Levenshtein distance. Spell-checkers, DNA alignment, diff tools all descend from it.

The state

Let dp[i][j] = edit distance between first i chars of word1 and first j chars of word2. Answer is dp[m][n].

Grid is (m+1) × (n+1) — row 0 and column 0 represent empty prefixes.

Base cases

• dp[i][0] = i — delete all i chars.
• dp[0][j] = j — insert all j chars.

The transition

Compare word1[i-1] and word2[j-1]:

• Match: dp[i][j] = dp[i-1][j-1]. Free — inherit diagonal.
• Differ: pay 1 + min of three moves — delete, insert, substitute.

Each cell depends on top, left, top-left. Fill row by row, left to right.

Reading the operations

Walk backward from dp[m][n] to dp[0][0], checking which neighbor produced each value. Same trick used in git's diff.

Common pitfalls

• Off-by-one indexing. dp[i][j] compares word1[i-1] to word2[j-1].
• Forgetting the match case is free, not 1.
• Naive recursion without memoization is exponential.

Space optimization

Each row depends only on the previous row. Collapse to two 1D arrays for O(min(m, n)) space.

Try it

1. Modify edit_distance to also return the sequence of operations by backtracking after the DP fill.
2. Solve Longest Common Subsequence with the same 2D template: match → dp[i-1][j-1] + 1, mismatch → max(dp[i-1][j], dp[i][j-1]).