Самая длинная палиндромная подпоследовательность — разбор

1. Идея

Нужно найти максимальную длину подпоследовательности строки s, которая читается одинаково слева направо и справа налево.

Ключевая мысль: будем решать задачу для всех подстрок s[l..r].

Обозначим dp[l][r] — длину самой длинной палиндромной подпоследовательности на отрезке от l до r включительно.

Тогда ответом будет dp[0][n - 1].

2. Наблюдения

Рассмотрим подстроку s[l..r].

Случай 1: s[l] == s[r]

Если крайние символы совпадают, их можно поставить по краям палиндрома. Тогда внутри остается найти палиндромную подпоследовательность в s[l+1..r-1].

Получаем:

• если длина отрезка равна 2, то ответ равен 2;
• иначе dp[l][r] = dp[l + 1][r - 1] + 2.

Случай 2: s[l] != s[r]

Если крайние символы разные, то оба одновременно на концах одного палиндрома стоять не могут.

Значит, оптимальный ответ получится в одном из двух вариантов:

• либо не берем символ s[l], тогда смотрим dp[l + 1][r];
• либо не берем символ s[r], тогда смотрим dp[l][r - 1].

Тогда:

dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

База

Если l == r, то подстрока состоит из одного символа, а один символ сам по себе палиндром.

Значит:

dp[i][i] = 1

3. Алгоритм

Будем заполнять таблицу динамики по возрастанию длины отрезка.

1. Считываем строку s, находим n.
2. Создаем таблицу dp размера n x n, изначально заполненную нулями.
3. Для всех i ставим dp[i][i] = 1.
4. Перебираем длину отрезка len от 2 до n.
5. Для каждого левого конца l находим правый конец r = l + len - 1.
6. Если s[l] == s[r]:
   • если len == 2, то dp[l][r] = 2;
   • иначе dp[l][r] = dp[l + 1][r - 1] + 2.
7. Иначе:
   • dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]).
8. Выводим dp[0][n - 1].

4. Почему это работает

Докажем, что динамика действительно считает ответ правильно.

Рассмотрим любой отрезок s[l..r].

База

Если l == r, то на отрезке один символ. Самая длинная палиндромная подпоследовательность имеет длину 1. Значит, dp[i][i] = 1 верно.

Переход

Если s[l] == s[r]

Тогда эти два символа могут быть крайними символами палиндромной подпоследовательности. Между ними нужно взять палиндромную подпоследовательность внутри отрезка s[l+1..r-1]. Ее максимальная длина равна dp[l+1][r-1], значит общая длина будет dp[l+1][r-1] + 2.

Для отрезка длины 2 внутренней части нет, поэтому ответ просто 2.

Если s[l] != s[r]

Тогда крайние символы не могут одновременно стоять по краям одного палиндрома. Значит, в оптимальном ответе хотя бы один из них не используется.

• Если не используется левый символ, остается задача на s[l+1..r].
• Если не используется правый символ, остается задача на s[l..r-1].

Берем лучший из этих двух вариантов, то есть max(dp[l+1][r], dp[l][r-1]).

Порядок вычисления

Все значения dp[l][r] зависят только от более коротких отрезков:

• dp[l+1][r-1]
• dp[l+1][r]
• dp[l][r-1]

Поэтому если идти по длине отрезка от меньшей к большей, в момент вычисления dp[l][r] все нужные значения уже известны.

Следовательно, после заполнения таблицы значение dp[0][n-1] равно длине самой длинной палиндромной подпоследовательности всей строки.

5. Сложность

Пусть n — длина строки.

• Количество состояний dp[l][r] равно n * n.
• Каждое состояние вычисляется за O(1).

Итоговая сложность:

• по времени: O(n^2)
• по памяти: O(n^2)

При n <= 1000 это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = (int)s.size();

    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            if (s[l] == s[r]) {
                if (len == 2) {
                    dp[l][r] = 2;
                } else {
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                }
            } else {
                dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
            }
        }
    }

    cout << dp[0][n - 1] << '\n';
    return 0;
}

7. Код на Python 3

s = input().strip()
n = len(s)

dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = 1

for length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1
        if s[l] == s[r]:
            if length == 2:
                dp[l][r] = 2
            else:
                dp[l][r] = dp[l + 1][r - 1] + 2
        else:
            dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

print(dp[0][n - 1])