DP: LCS and edit distance

How different are two strings? A 2-D DP grid over their prefixes. The engine behind diff, spell-check, and DNA alignment.

The grid: three moves per cell

• dp[i][j] = compare first i chars of A with first j of B
• Delete (up+1) · Insert (left+1) · Match/Substitute (diagonal + 0 or 1)
• Base: empty → prefix = that many inserts/deletes
• LCS = same grid, match extends the diagonal, no substitution

Watch the grid fill

kitten → sitting. Teal = free diagonal (chars equal). Orange path = the alignment: sub k→s, keep itt, sub e→i, keep n, +g. Distance 3.

Exponential → polynomial

Length 12: naive 42,000 calls, DP 169 cells → 250× less.

Alignment = a path through the grid

• Every corner-to-corner path is an alignment; cost = non-free steps
• diff = LCS of the lines; edits = m + n − 2·LCS (no substitution)
• Long sequences: banded DP, Hirschberg (O(min) space), seed-and-extend (BLAST)
• Rolling array → O(min(m,n)) space if you only need the distance

Takeaway

Sequence problems are cheapest-paths through a grid. One diagram serves coding theory, biology, and file diffing. Next: backtracking — search the space of choices, prune dead ends.