1. Идея

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

Эталонное решение делает это не напрямую, а через другую величину: ищет длину наибольшей палиндромной подпоследовательности строки.

Почему это полезно:

• символы этой подпоследовательности уже можно оставить "как есть";
• все остальные символы придется как-то "достроить" вставками, чтобы получился палиндром.

Если длина наибольшей палиндромной подпоследовательности равна L, а длина строки равна n, то ответ равен n - L.

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

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

Наблюдение 1

Для любой подстроки s[l..r] можно независимо посчитать длину наибольшей палиндромной подпоследовательности внутри нее.

Обозначим:

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

Тогда нужен ответ для всей строки: dp[0][n - 1].

Наблюдение 2

Если рассматриваем крайние символы подстроки:

• если s[l] == s[r], то их можно поставить на края палиндрома;
• если s[l] != s[r], то одновременно взять оба края в один палиндром нельзя, значит нужно отбросить либо левый, либо правый символ.

Отсюда получается переход.

Наблюдение 3

База динамики:

• если подстрока состоит из одного символа, то это уже палиндром длины 1, значит dp[i][i] = 1.

Для длины 2:

• если два символа равны, то палиндром длины 2;
• иначе максимальная палиндромная подпоследовательность имеет длину 1.

В эталонном решении случай длины 2 при равных символах обработан отдельно.

Наблюдение 4

Почему ответ именно n - dp[0][n - 1]?

Наибольшая палиндромная подпоследовательность — это максимальное количество символов, которые можно оставить внутри будущего палиндрома без изменений порядка. Остальные n - L символов не помещаются в этот "каркас" палиндрома, и для каждого из них потребуется по одной вставке пары/соответствия. В итоге минимальное число вставок равно n - L.

3. Алгоритм

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

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

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

Докажем корректность динамики.

Что хранит dp[l][r]

По определению, dp[l][r] — это длина наибольшей палиндромной подпоследовательности в подстроке s[l..r].

Нужно показать, что переходы вычисляют это значение правильно.

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

Тогда эти два символа можно поставить на левый и правый край некоторой палиндромной подпоследовательности.

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

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

Значит, в этом случае:

• dp[l][r] = 2, если len == 2;
• dp[l][r] = dp[l + 1][r - 1] + 2, если len > 2.

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

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

Значит, наибольшая палиндромная подпоследовательность в s[l..r] либо:

• целиком лежит в s[l+1..r], либо
• целиком лежит в s[l..r-1].

Поэтому надо взять максимум из этих двух вариантов:

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

То есть:

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

Почему итоговый ответ равен n - dp[0][n - 1]

Пусть L = dp[0][n - 1] — длина наибольшей палиндромной подпоследовательности.

Эти L символов можно рассматривать как основу будущего палиндрома. Остальные n - L символов не входят в эту основу, и чтобы вся строка стала палиндромом, для них нужно добавить недостающие симметричные символы вставками.

Известный факт для этой задачи: минимальное число вставок равно количеству символов вне наибольшей палиндромной подпоследовательности, то есть n - L.

Следовательно, алгоритм выводит правильный ответ.

5. Сложность

Размер таблицы dp — n x n.

• Временная сложность: O(n^2), потому что каждая пара l, r обрабатывается один раз.
• Используемая память: O(n^2) на таблицу динамики.

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

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

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 << n - 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(n - dp[0][n - 1])