Edit Distance
Given two strings, print the fewest single-character edits needed to turn the first into the second. An edit is an insertion, a deletion, or a replacement.
The same grid as the previous problem, with a minimum instead of a maximum and a cost instead of a credit. Each neighbour is one edit, chosen by which string it consumes: deleting takes one character of the first, so it is the cell above; inserting matches a character of the second, so it is the cell to the left; replacing consumes one of each, so it is the diagonal.
When the characters already match, take the diagonal at NO cost. That fourth case is the one people forget, and without it the answer is simply the length difference.