Problem. Given strings a and b, return the length of their longest common subsequence (LCS): the longest sequence of
characters that appears in both, in the same order, not necessarily contiguous.
a = "abcde", b = "ace" → 3 ("ace")
a = "abc", b = "def" → 0
This is the first two-sequence DP: the state is a pair (i, j), "the LCS of the first i characters of a and the first j of b". Compare the last characters: if they match, they can end the common subsequence; if not, at least one of them isn't in it, so drop one and take the better.
ML context. LCS measures ordered overlap between sequences. ROUGE-L, a standard summarisation metric, is an F-score built
on the LCS between a generated summary and a reference (Change D). diff and version control show changes between files as an LCS of
lines (Change A). Lesson 12.12's edit distance is a close relative used for word error rate.