On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:
if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] := minimum ( d[i-1, j] + 1, // a deletion d[i, j-1] + 1, // an insertion d[i-1, j-1] + 1 // a substitution ) }
As you can see, the algorithm always chooses the value from the upper-left neighbour if there is a match, saving some memory accesses, ALU operations and comparisons.
However, deletion (or insertion) may result in a smaller value, thus the algorithm is locally incorrect, i.e. it breaks with the optimality criterion. But maybe the mistake does not change the end result -- it might be cancelled out.
Is this micro-optimisation valid, and why (not)?