Разбор задачи «Стирание палиндромов»

1. Идея

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

Ключевая идея — динамическое программирование по подотрезкам.

Будем считать dp[l][r] — минимальное количество ходов, чтобы удалить все плитки на отрезке от l до r включительно. Ответом будет dp[0][n - 1].

Главный вопрос: как пересчитывать dp[l][r]? Рассмотрим левую плитку c[l]. С ней в оптимальном плане может происходить ровно одно из трёх:

• она удаляется отдельным ходом;
• она удаляется в паре со следующей плиткой c[l+1] (если та того же цвета);
• она «уносится» вместе с равной плиткой c[k], стоящей дальше (k >= l+2), когда середина между ними уже стёрта.

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

Наблюдение 1. База

Одна плитка сама по себе палиндром, поэтому dp[i][i] = 1.

Наблюдение 2. Простейший переход

Всегда можно удалить первую плитку отрезка отдельно, а потом всё остальное: dp[l][r] <= 1 + dp[l + 1][r].

Наблюдение 3. Соседняя одинаковая пара

Если c[l] == c[l+1], эти две плитки образуют палиндром длины 2 и удаляются за один ход: dp[l][r] <= 1 + dp[l + 2][r] (если l+2 > r, остаётся только эта пара — ответ 1).

Наблюдение 4. Склейка с дальней равной плиткой

Пусть c[l] == c[k] для некоторого k >= l+2. Тогда:

1. сначала удаляем середину [l+1 .. k-1] за dp[l+1][k-1] ходов;
2. после этого c[l] оказывается вплотную к c[k]; будучи одного цвета, c[l] уносится тем же ходом, что стирает палиндром, начинающийся с c[k], без отдельной платы;
3. остаётся независимо удалить хвост [k+1 .. r].

Получаем dp[l][r] <= dp[l + 1][k - 1] + dp[k + 1][r] (пустые части дают 0).

Наблюдение 5. Почему случаи 3 и 4 нельзя объединять

Соблазнительно перебирать k сразу с l+1. Но при k = l+1 середина пуста, и формула dp[l+1][k-1] + dp[k+1][r] превращается в dp[l+2][r] без +1 — то есть как будто пара c[l], c[l+1] стирается бесплатно. Это неверно: пару всё равно надо удалить отдельным ходом. Поэтому соседняя пара учитывается формулой из наблюдения 3 (с +1), а общий перебор k начинается с l+2.

Контрпример к «объединённому» варианту: для 2 2 правильный ответ 1, а ошибочная формула дала бы 0.

3. Алгоритм

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

1. Считать n и массив c.
2. Создать таблицу dp размера n x n, положить dp[i][i] = 1.
3. Для длины len от 2 до n, для каждого отрезка [l, r]:
   • dp[l][r] = 1 + dp[l + 1][r];
   • если c[l] == c[l + 1]: dp[l][r] = min(dp[l][r], 1 + (l+2 <= r ? dp[l + 2][r] : 0));
   • для k от l + 2 до r: если c[l] == c[k], то dp[l][r] = min(dp[l][r], dp[l + 1][k - 1] + (k+1 <= r ? dp[k + 1][r] : 0)).
4. Вывести dp[0][n - 1].

4. Сложность

O(n^2) состояний, для каждого перебор k за O(n):

• время: O(n^3);
• память: O(n^2).

При n <= 500 проходит.

5. Код на C++17

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }

    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;

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

            if (c[l] == c[l + 1]) {
                int inner = (l + 2 <= r) ? dp[l + 2][r] : 0;
                dp[l][r] = min(dp[l][r], 1 + inner);
            }

            for (int k = l + 2; k <= r; ++k) {
                if (c[l] == c[k]) {
                    int leftPart = dp[l + 1][k - 1];
                    int rightPart = (k + 1 <= r) ? dp[k + 1][r] : 0;
                    dp[l][r] = min(dp[l][r], leftPart + rightPart);
                }
            }
        }
    }

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

6. Код на Python 3

n = int(input())
c = list(map(int, input().split()))

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

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

        if c[l] == c[l + 1]:
            inner = dp[l + 2][r] if l + 2 <= r else 0
            dp[l][r] = min(dp[l][r], 1 + inner)

        for k in range(l + 2, r + 1):
            if c[l] == c[k]:
                left = dp[l + 1][k - 1]
                right = dp[k + 1][r] if k + 1 <= r else 0
                dp[l][r] = min(dp[l][r], left + right)

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