Two sequences and a grid

How different are two words? Turning kitten into sitting takes three edits: substitute k for s, substitute e for i, insert g. Computing that number is what a spell checker does, and what git diff does for lines instead of letters.

The state is a position in each

When a problem involves two sequences, the state is almost always how far you have got through each:

d[i][j] = edits to turn the first i letters of A into the first j of B

If the current letters match, nothing is spent:

d[i][j] = d[i - 1][j - 1]

If they do not, spend one edit and take the cheapest of the three ways to make progress:

d[i][j] = 1 + min(
    d[i - 1][j],       # delete from A
    d[i][j - 1],       # insert into A
    d[i - 1][j - 1]    # substitute
)

Reading the grid

Fill row by row, left to right. Each cell looks up, left, and diagonally back, all of which are already filled.

      ""  s   i   t   t   i   n   g
  ""   0  1   2   3   4   5   6   7
  k    1  1   2   3   4   5   6   7
  i    2  2   1   2   3   4   5   6
  t    3  3   2   1   2   3   4   5

The answer is the bottom right corner.

The family

Any problem whose state is a cell depending on up, left and diagonal is this shape:

• Longest common subsequence: take the diagonal on a match, otherwise the better of up and left.
• Edit distance: as above.
• Sequence alignment: the same, with different costs per operation.

Note the difference from a substring, which must be contiguous and is a different and simpler recurrence. A problem saying "not necessarily adjacent" is telling you which one it wants.