Изменения
→Формула
j&&;&i = 0,\ j > 0\\
\rm{min}(\\
&\rm{D}(i, j - 1) + 1w(ε, S_2[j])\\&\rm{D}(i - 1, j) + 1w(S_1[i], ε)&;&j > 0,\ i > 0\\
&\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\
)
</tex>,
где <tex>\rm{m}(a,b)</tex> равна нулю, если <tex>a = b</tex> и единице цену операции замены в противном случае; <tex>\min(a, b, c)</tex> возвращает наименьший из аргументов. w(ε, b) — цена вставки символа b, w(a, ε) — цена удаления символа a.
=== Доказательство ===
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.
== Алгоритм Вагнера — Фишера ==
