Разбор задачи «Странный принтер»

1. Идея

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

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

Будем считать dp[l][r] — минимальное количество операций, чтобы напечатать подстроку s[l..r].

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

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

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

Если подстрока состоит из одного символа, то нужен ровно один проход принтера:

• dp[i][i] = 1

Наблюдение 2. Наивный переход

Для подстроки s[l..r] можно сначала отдельно напечатать символ s[l], а потом напечатать остаток s[l+1..r].

Тогда:

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

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

Наблюдение 3. Если встречается такой же символ

Пусть для некоторого k выполнено s[k] == s[l].

Тогда символы в позициях l и k можно напечатать в одной и той же операции. Из-за этого иногда удаётся сэкономить одну операцию.

Как это учесть:

• сначала печатаем часть между ними: s[l+1..k-1]
• потом печатаем подстроку s[k..r] так, чтобы символ в позиции k печатался вместе с символом в позиции l

Отсюда переход:

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

Если между l и k нет символов, то первая часть пустая и её стоимость равна 0.

3. Алгоритм

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

Шаги

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

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

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

Что означает dp[l][r]

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

Почему переход 1 + dp[l+1][r] корректен

Можно сделать одну операцию, которая напечатает символ s[l] на позиции l, а затем отдельно напечатать остаток s[l+1..r].

Значит, такой способ всегда существует.

Почему можно объединять позиции l и k, если s[k] == s[l]

Если символы одинаковые, то нет необходимости печатать их двумя независимыми операциями. Можно устроить процесс так, чтобы операция, которая печатает символ в позиции k, одновременно покрыла и позицию l.

Но между ними находятся символы s[l+1..k-1], которые в итоговой строке могут быть другими. Поэтому их нужно подготовить отдельно — именно за это отвечает dp[l+1][k-1].

После этого остаётся напечатать часть s[k..r]. Внутри этой печати символ в позиции k уже будет равен s[l], и его можно совместить с позицией l.

Именно поэтому стоимость получается:

• стоимость середины
• плюс стоимость правой части, где позиция k уже участвует

то есть dp[l+1][k-1] + dp[k][r].

Почему перебор всех k даёт оптимум

В оптимальном решении для подстроки s[l..r] символ в позиции l либо:

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

Мы перебираем все такие случаи, значит, не пропускаем оптимальное решение.

5. Сложность

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

• Состояний dp[l][r] всего O(n^2)
• Для каждого состояния перебирается k, то есть ещё O(n)

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

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

При n <= 100 это легко проходит.

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;

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

            for (int k = l + 1; k <= r; k++) {
                if (s[k] == s[l]) {
                    int middle = 0;
                    if (k > l + 1) {
                        middle = dp[l + 1][k - 1];
                    }
                    dp[l][r] = min(dp[l][r], middle + dp[k][r]);
                }
            }
        }
    }

    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
        dp[l][r] = 1 + dp[l + 1][r]

        for k in range(l + 1, r + 1):
            if s[k] == s[l]:
                middle = 0
                if k > l + 1:
                    middle = dp[l + 1][k - 1]
                value = middle + dp[k][r]
                if value < dp[l][r]:
                    dp[l][r] = value

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