Lesson 31.2 · DP on Strings and Sequences
Two Sequences: LCS and Edit Distance
dp[i][j] compares the first i characters of A with the first j of B. Matching characters extend the diagonal; otherwise take the best of dropping one character from either side.
16 min
Think of it like this
Comparing two drafts of an essay line by line to find what stayed the same: when lines match you keep both; when they don't, you decide which draft's line to skip.
1.LCS
dp[i][j] = longest common subsequence of A[0..i) and B[0..j). If A[i − 1] == B[j − 1], dp[i][j] = dp[i − 1][j − 1] + 1. Otherwise max(dp[i − 1][j], dp[i][j − 1]). Row 0 and column 0 are 0 (empty prefix).
A = "ace" (rows), B = "abcde" (columns)Step 1/4Empty prefixes share nothing: row ∅ and column ∅ are 0.
2.Edit distance
dp[i][j] = fewest insert/delete/replace operations to turn A[0..i) into B[0..j). Base: dp[i][0] = i (delete all), dp[0][j] = j (insert all). If the last characters match, dp[i − 1][j − 1]; otherwise 1 + min(replace dp[i − 1][j − 1], delete dp[i − 1][j], insert dp[i][j − 1]).
These tables power diff tools, spell checkers and DNA alignment. Both need O(m × n) time; memory drops to O(min(m, n)) with two rolling rows.
Remember
- State: (i, j) prefixes.
- Match → diagonal; mismatch → best neighbour.
- Rolling rows for memory.
Common mistakes
- Off-by-one between string index and table index (A[i − 1] for row i).