Изменения
→Доказательство
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — неоптимально (если мы заменили <tex>x </tex> на <tex>y</tex>, потом <tex>y </tex> на <tex>z</tex>, выгоднее было сразу заменить <tex>x </tex> на <tex>z</tex>).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
