DP problems — edit distance (Levenshtein)

WHAT is it?

We define a 2D table:

$dp[i][j] = \text{edit distance between the first } i \text{ chars of } A \text{ and the first } j \text{ chars of } B$

So $dp[m][n]$ is our final answer, and $dp[0][0]=0$ (two empty strings cost nothing).

WHY does a recurrence even exist?

The last move is one of:

1. Characters match (A[i-1] == B[j-1]): no edit needed for this position → cost passes through from $dp[i-1][j-1]$.
2. Substitute A[i-1] → B[j-1]: cost $1 +$ the cost of aligning the smaller prefixes $dp[i-1][j-1]$.
3. Delete A[i-1] (it's an extra char in A): cost $1 + dp[i-1][j]$.
4. Insert B[j-1] (it's needed in B): cost $1 + dp[i][j-1]$.

We take the minimum because we want the cheapest way.

HOW to derive the recurrence from scratch

Why this is correct: every conversion ends with exactly one of the four cases above, each reduces to a strictly smaller subproblem, and we minimise — so we never miss the optimum (this is optimal substructure + overlapping subproblems).

Complexity (the 80/20 takeaway)

• Time: $O(m \cdot n)$ — we fill each cell once in $O(1)$.
• Space: $O(m \cdot n)$ for the full table, or $O(\min(m,n))$ if you only keep the previous row (you only ever read row $i-1$ and column $j-1$).

Worked Example 1 — "horse" → "ros" (answer = 3)

We fill the table row by row. Let $A=$horse (rows), $B=$ros (cols).

• Why $dp[2][2]=1$? A[1]='o', B[1]='o' match, so we copy the diagonal $dp[1][1]=1$. Why this step? Matching costs nothing, so the cost equals fixing the smaller prefixes "h"→"r".
• Why $dp[5][3]=3$? 'e' ≠ 's', so $1+\min(dp[4][2],dp[4][3],dp[5][2]) = 1+\min(3,2,4)=3$. Why this step? Cheapest predecessor is the delete path (delete e), giving the final 3.
• Reading edits back: substitute h→r? No — actual optimal path is delete h, delete r, substitute e→s (3 edits), matching $dp[5][3]=3$.

Worked Example 2 — "sunday" → "saturday" (answer = 3)

Key cells:

• The shared s...n...day structure means many matches pass straight down the diagonal.
• We need to insert a and t, and substitute n→r. That's $2 + 1 = 3$.

Why this is 3 and not more? Because the long common subsequence s..day aligns for free; only 3 positions actually differ in a way that needs work. Why this step matters: edit distance secretly rewards long shared subsequences.

Worked Example 3 — Forecast-then-Verify

Common Mistakes

Active Recall

Connections

• Dynamic Programming — edit distance is a canonical 2D-table DP.
• Longest Common Subsequence — closely related; LCS aligns matches, edit distance counts mismatches.
• Optimal Substructure — the property that makes the recurrence valid.
• Overlapping Subproblems — why memoisation/tabulation beats naive recursion.
• Recursion and Memoization — top-down alternative to the bottom-up table.
• Sequence Alignment — bioinformatics generalisation (Needleman–Wunsch) with weighted costs.
• Space Optimization in DP — the rolling-row trick to reach $O(\min(m,n))$ space.

Concept Map

Hinglish (regional understanding)