3622
правки
Изменения
м
Нет описания правки
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида <tex>S(i, i)</tex>) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов <tex>S(i, i + 1)</tex> возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.
Пусть теперь нам дана подпоследовательность <tex>S(i, j)</tex>. Если первый <tex>(S[i])</tex> и последний <tex>(S[j])</tex> элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность <tex>S(i, j – - 1)</tex> или <tex>S(i + 1, j)</tex> — то есть мы сведем задачу к подзадаче: <tex>L[i][j] = max(L[i][j - 1], L[i + 1][j])</tex>. Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи <tex>S(i + 1, j - 1):
L[i][j] = L[i + 1][j - 1] + 2</tex>.
== Пример ==
