Статья Автор: Деникина Н.В., Деникин А.В.

Вопрос 24. Динамическое программирование

Идея

Динамическое программирование (ДП) — это когда мы разбиваем задачу на подзадачи и используем ответы на уже решённые подзадачи для решения следующих.

Создаём массив dp такой же длины, как строка. Значение dp = максимальная длина правильной цепочки, которая заканчивается на символе s[i].

Заполняем массив слева направо. Для каждой позиции проверяем: может ли здесь заканчиваться какой-то из допустимых фрагментов? Если да — прибавляем длину этого фрагмента к значению dp в позиции перед ним.

Пример: цепочки из XY, YZ, YZZ

Задача: найти максимальную длину подстроки, составленной из фрагментов XY, YZ и YZZ, соединённых в любом порядке.

Важно: Фрагменты пересекаются! Например, XY заканчивается на Y, а YZ начинается с Y.
 

N = len(s)
dp = [0] * N  # массив нулей

for i in range(N):
    # Проверяем: заканчивается ли на s[i] фрагмент длины 2?
    if s[i-1:i+1] in ["XY", "YZ"]:
        dp[i] = 2 + dp[i-2]

    # Проверяем: заканчивается ли на s[i] фрагмент длины 3?
    if s[i-2:i+1] == "YZZ":
        dp[i] = max(dp[i], 3 + dp[i-3])

print(max(dp))  # ответ — наибольшее значение в dp

Разбор на примере

Строка: XYYYZXYYZZX

индекс 0 1 2 3 4 5 6 7 8 9 10
s X Y Y Y Z X Y Y Z Z X
dp 0 2 0 0 2 0 4 0 6 7 0

Разберём ключевые моменты:

  • dp[1] = 2 — нашли XY (позиции 0–1), до него ничего нет → 2 + 0 = 2
  • dp[4] = 2 — нашли YZ (позиции 3–4), dp[2] = 0 → 2 + 0 = 2
  • dp[6] = 4 — нашли XY (позиции 5–6), dp[4] = 2 → 2 + 2 = 4
  • dp[8] = 6 — нашли YZ (позиции 7–8), dp[6] = 4 → 2 + 4 = 6
  • dp[9] = 7 — нашли YZZ (позиции 7–9), dp[6] = 4 → 3 + 4 = 7 

Ответ: 7

Почему это работает с отрицательными индексами?

Когда i маленький (0 или 1), в Python dp[-1] и dp[-2] — это последние элементы массива, которые равны 0. А срезы вроде s[-1:1] дают пустую строку. Так что условия автоматически не срабатывают, и граничные случаи обрабатывать отдельно не нужно!


Когда использовать?

  • Когда допустимые фрагменты пересекаются (один заканчивается тем же, чем другой начинается)
  • Когда метод замен не работает из-за потери символов
  • Когда задачу можно описать как «собери цепочку из заданных кусочков»
Печать