Изменения

Перейти к: навигация, поиск

Динамическое программирование

1 байт убрано, 21:52, 29 февраля 2012
Нет описания правки
# <tex> s(i) = s(j), тогда d(i, j) = d(i + 1, j - 1) + 2 </tex> <br />
Доказательство:<br />
# Так <tex>s(i) \neq s(j)</tex>, символы $s(i)$ и $s(j)$ не могут входит в максимальный подпвлиндром подпалиндром одновременно, то есть либо $s(i)$ входят в максимальный подпвлиндром подпалиндром(тогда его длина $d[i, j - 1]$), либо $s(j)$ входи в максимальный подпвлиндром подпалиндром (тогда его длина $d[i + 1, j]$), либо оба не входят в максимальный подпвлиндром подпалиндром (тогда его длина $= d[i, j - 1] = d[i + 1, j]$). <br /># Данное равенство следует из факта, что выгодно включить в максимальный подпвлиндром подпалиндром символы $s(i)$ и $s(j)$.
=== Примеры задач ===
48
правок

Навигация