Изменения
Нет описания правки
== Динамическое программирование ==
=== Решение ===
Обозначим как <tex>a_{i, j}</tehtex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex>i</tex> и <tex>j</tex> соответственно.Получаем следующее рекуррентное соотношение:
*<tex>a_{i, j} = a_{i - 1, j - 1} + 1</tex>, если <tex>s[i] = s[j]</tex> (соответствующие элементы последовательностей равны)
*<tex>a_{i, j} = max(a_{i, j - 1}, a_{i - 1, j})</tex>, если <tex>s1[i] <> s2[j]</tex> (соответствующие элементы последовательностей не равны).
