Изменения

Как частный случай, так и задачу для произвольных <tex>w</tex>, решает алгоритм Вагнера — Вагнера-Фишера, приведённый ниже. Здесь и ниже мы считаем, что все <tex>w</tex> неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ <tex>x</tex> на <tex>y</tex>, а потом с <tex>y</tex> на <tex>z</tex> не лучше, чем сразу <tex>x</tex> на <tex>z</tex>).