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