Problem. Given strings a and b, return the minimum number of operations to turn a into b, where an operation is insert a
character, delete a character, or substitute one character for another.
a = "horse", b = "ros" → 3 (horse → rorse → rose → ros)
a = "intention", b = "execution" → 5
Like lesson 12.11's LCS, it's a two-sequence DP over prefixes. Look at the last characters: if they're equal, they cost nothing; otherwise the last operation was a deletion (of a's last char), an insertion (of b's last char) or a substitution.
ML context. Edit distance is the standard similarity for short strings: spelling correction and fuzzy label matching (lesson 12.15), deduplicating near-identical names, and evaluation: word error rate (WER) for speech recognition and character error rate (CER) for OCR are edit distances over words or characters, divided by the reference length (Change D).