1. Идея

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

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

Обозначим dp[l][r] — минимальное количество вставок, необходимое, чтобы подстрока s[l..r] стала палиндромом.

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

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

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

Случай 1: крайние символы равны

Если s[l] == s[r], то эти два символа уже могут стоять на симметричных местах в палиндроме. Значит, ничего добавлять из-за них не нужно, и задача сводится к внутренней подстроке:

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

Если внутри уже ничего нет или один символ, то ответ равен 0.

Случай 2: крайние символы различны

Если s[l] != s[r], то в палиндроме они не могут сразу стать парой.

Тогда есть два естественных варианта:

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

Это приводит к переходу:

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

Почему именно так:

• если "сочетаем" символ s[l], то дальше нужно сделать палиндром из s[l + 1..r];
• если "сочетаем" символ s[r], то дальше нужно сделать палиндром из s[l..r - 1];
• за текущую вставку добавляем 1.

База

Для подстроки длины 1 ничего вставлять не нужно: один символ уже палиндром.

То есть dp[l][l] = 0.

3. Алгоритм

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

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

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

Докажем корректность переходов.

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

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

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

Добавлять что-то специально для s[l] и s[r] не нужно, поэтому:

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

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

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

В итоговом палиндроме крайние символы должны совпадать. Так как s[l] и s[r] различны, хотя бы один из них не сможет сразу образовать пару с другим. Значит, придётся сделать вставку.

Есть два оптимальных типа первого шага:

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

После этого остаётся соответственно задача для одной из подстрок:

• s[l + 1..r]
• s[l..r - 1]

Из двух вариантов выбираем лучший:

dp[l][r] = 1 + min(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] все нужные значения уже известны.

Следовательно, алгоритм корректно находит ответ для всей строки.

5. Сложность

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

• Состояний в динамике: n * n
• Каждое состояние считается за O(1)

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

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

При n <= 2000 такое решение подходит.

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 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 (l + 1 <= r - 1) {
                    dp[l][r] = dp[l + 1][r - 1];
                } else {
                    dp[l][r] = 0;
                }
            } else {
                dp[l][r] = 1 + min(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 length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1
        if s[l] == s[r]:
            if l + 1 <= r - 1:
                dp[l][r] = dp[l + 1][r - 1]
            else:
                dp[l][r] = 0
        else:
            dp[l][r] = 1 + min(dp[l + 1][r], dp[l][r - 1])

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