В Википедии дается реализация восходящей схемы динамического программирования для расстояния редактирования. Это не следует определению полностью; внутренние ячейки вычисляются следующим образом:
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
)
}
Как видите, алгоритм всегда выбирает значение из верхнего левого соседа, если есть совпадение, сохраняя некоторые обращения к памяти, операции ALU и сравнения.
Однако удаление (или вставка) может привести к меньшему значению, поэтому алгоритм локально некорректен, то есть нарушает критерий оптимальности. Но, возможно, ошибка не меняет конечный результат - он может быть отменен.
Является ли эта микрооптимизация действительной и почему (нет)?