Минимум разрезов на палиндромы

1. Идея

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

Например:

• строка aba уже палиндром, значит разрезов 0;
• строку ab можно разбить только как a | b, значит нужен 1 разрез.

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

Удобно решать задачу динамическим программированием в два этапа:

1. заранее определить, какие подстроки являются палиндромами;
2. по этим данным посчитать минимальное число разрезов для каждого префикса строки.

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

Наблюдение 1. Как проверить, что подстрока — палиндром

Подстрока s[l..r] является палиндромом, если:

• s[l] == s[r], и
• внутренняя подстрока s[l+1..r-1] тоже палиндром.

Отсюда сразу получается динамика по подотрезкам.

Базовые случаи:

• любая подстрока длины 1 — палиндром;
• подстрока длины 2 — палиндром, если её символы равны.

Наблюдение 2. Как считать минимальные разрезы

Пусть cut[i] — минимальное число разрезов, чтобы разбить префикс длины i, то есть строку s[0..i-1], на палиндромы.

Тогда рассмотрим последний кусок в таком разбиении. Пусть он начинается в позиции j и заканчивается в i - 1.

Если s[j..i-1] — палиндром, то до него уже должен быть оптимально разбит префикс s[0..j-1].

Тогда:

• если j == 0, то весь префикс s[0..i-1] сам палиндром, разрезов не нужно, cut[i] = 0;
• иначе можно взять cut[j] + 1, потому что между частями нужен ещё один разрез.

Наблюдение 3. Почему cut[0] = -1

В эталонном решении используется немного необычная и удобная инициализация:

• cut[0] = -1.

Это означает: у пустой строки как будто на один разрез меньше, чем у обычной строки.

Зачем это нужно? Чтобы формула cut[j] + 1 работала даже в случае, когда палиндром начинается с самого начала строки.

Хотя в коде отдельно обрабатывается случай pal[0][i - 1], такая инициализация всё равно хорошо согласуется с идеей динамики.

3. Алгоритм

Шаг 1. Строим таблицу палиндромов

Создадим двумерный массив pal, где:

• pal[l][r] = True, если подстрока s[l..r] — палиндром;
• иначе False.

Заполняем его по возрастанию длины подстроки:

• для каждой длины len от 1 до n;
• для каждого левого конца l;
• правый конец r = l + len - 1.

Правило:

• если s[l] != s[r], то палиндрома нет;
• если s[l] == s[r], то:
  • при len <= 2 подстрока палиндром;
  • иначе нужно, чтобы pal[l + 1][r - 1] было истинно.

Шаг 2. Считаем минимальные разрезы

Создадим массив cut длины n + 1.

• cut[i] — минимальное число разрезов для первых i символов;
• изначально заполним большими значениями;
• cut[0] = -1.

Далее для каждого i от 1 до n:

1. Если s[0..i-1] — палиндром, то cut[i] = 0.
2. Иначе перебираем j от 1 до i - 1:
   • если s[j..i-1] — палиндром,
   • то можно обновить: cut[i] = min(cut[i], cut[j] + 1).

Ответ — cut[n].

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

Докажем корректность по частям.

Корректность таблицы pal

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

• Если её длина 1, это палиндром.
• Если длина 2, это палиндром тогда и только тогда, когда символы равны.
• Если длина больше 2, то подстрока является палиндромом тогда и только тогда, когда:
  • крайние символы равны;
  • внутренняя часть s[l+1..r-1] тоже палиндром.

Именно это правило используется при заполнении массива pal. Поскольку мы идём по возрастанию длины, к моменту вычисления pal[l][r] значение pal[l+1][r-1] уже известно.

Значит, таблица pal заполняется верно.

Корректность динамики cut

Докажем, что cut[i] действительно равно минимальному числу разрезов для префикса s[0..i-1].

Рассмотрим любое оптимальное разбиение этого префикса на палиндромы. У него есть последний кусок: s[j..i-1].

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

• если j = 0, весь префикс сам палиндром, значит разрезов 0;
• если j > 0, то до позиции j - 1 расположен некоторый префикс, который в оптимальном решении разбит минимально, а между ним и последним куском стоит ещё один разрез. Значит число разрезов равно cut[j] + 1.

Мы перебираем все возможные j, для которых s[j..i-1] — палиндром, и берём минимум. Следовательно, получаем наименьшее возможное число разрезов.

Значит, cut[i] вычисляется правильно для всех i, и итоговый ответ cut[n] корректен.

5. Сложность

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

Время

1. Построение pal:

   • O(n^2), потому что рассматриваются все подстроки.

2. Вычисление cut:

   • внешний цикл по i,
   • внутренний по j,
   • всего O(n^2).

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

• O(n^2) по времени.

Память

• таблица pal занимает O(n^2);
• массив cut занимает O(n).

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

• O(n^2).

Для n <= 2000 это подходит.

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<bool>> pal(n, vector<bool>(n, false));

    for (int len = 1; 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 || pal[l + 1][r - 1]) {
                    pal[l][r] = true;
                }
            }
        }
    }

    vector<int> cut(n + 1, n);
    cut[0] = -1;

    for (int i = 1; i <= n; i++) {
        if (pal[0][i - 1]) {
            cut[i] = 0;
        } else {
            for (int j = 1; j < i; j++) {
                if (pal[j][i - 1]) {
                    cut[i] = min(cut[i], cut[j] + 1);
                }
            }
        }
    }

    cout << cut[n] << '\n';
    return 0;
}

7. Код на Python 3

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

pal = [[False] * n for _ in range(n)]

for length in range(1, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1
        if s[l] == s[r]:
            if length <= 2 or pal[l + 1][r - 1]:
                pal[l][r] = True

cut = [n] * (n + 1)
cut[0] = -1

for i in range(1, n + 1):
    if pal[0][i - 1]:
        cut[i] = 0
    else:
        for j in range(1, i):
            if pal[j][i - 1]:
                cut[i] = min(cut[i], cut[j] + 1)

print(cut[n])