Dynamic Programming on Two Sequences
Longest common subsequence and edit distance both fill a grid where each cell asks one question about the last character of each string. The table gives the answer, and walking back through it gives the alignment that produced it.
What a learner can do afterwards
- Fill an edit distance table for two short words and read the answer off the corner
- Trace back through the table to recover the actual edits
- Say what each of the three choices in the recurrence corresponds to
1 · Read
Longest common subsequence and edit distance both fill a grid. Each row steps through one string and each column through the other. Every cell asks one question about the last character of each prefix.
Each cell picks the cheapest of three moves. Match or substitute pairs the two last characters. Delete skips one from the side string. Insert skips one from the top string.
Turn CAT into CUT. The corner of the table reads 1. The traceback pairs C with C, swaps A for U, and pairs T with T. One substitution is the whole answer.
Read the answer off the far corner, then walk back to recover the edits. Each step back names the move its cell chose.
Fill the grid with three choices per cell, read the corner, and trace back the edits.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.