Sequence Dynamic Programming

Sequence dynamic programming compares strings and lists by solving the problem for every pair of prefixes. The topic opens on that table, its extra row and column for the empty prefix, and the three neighbours each entry reads. A walkthrough fills the longest common subsequence table for two words and walks back to recover the letters, and a gotcha shows what the table does in three languages when the empty prefix is left out. A code card writes the table and the walk back in Python, Java and TypeScript. A second walkthrough computes an edit distance and names the edits. The topic then turns to a single sequence: the longest increasing subsequence in O(n²), then the idea behind the O(n log n) method that keeps the smallest tail for each length. An exercise compares two versions of a recipe line by line, the idea behind a diff.