ДП на подотрезках (интервальное ДП)

Когда ответ для отрезка собирается из ответов для его кусков: динамика по интервалам [i, j] с перебором точки разбиения.

Интервальное ДП — динамика, где состояние — это отрезок последовательности [i, j], а переход перебирает точку k, разбивающую отрезок на две части.

Зачем это нужно

Есть целый класс задач, где ответ для куска зависит от ответов для его подкусков: оптимальная расстановка скобок, удаление/слияние элементов, разрезание палки, «съедание» камней, восстановление палиндрома. Их объединяет структура: чтобы решить отрезок [i, j], мы выбираем, как разбить его на два меньших отрезка, и комбинируем их решения. Это интервальное ДП. Оно сложнее одномерного (состояние двумерное, есть перебор точки разбиения), но укладывается в понятный шаблон, который стоит освоить — он открывает доступ к задачам уровня Gold.

Идея «на пальцах»

Состояние dp[i][j] — оптимальный ответ для отрезка от i до j. Переход: перебираем точку разбиения k (где i ≤ k < j) и комбинируем ответы для левой части [i, k] и правой [k+1, j] плюс «стоимость стыка». Берём лучшее по всем k. Ключевой момент — порядок вычисления: считаем сначала короткие отрезки, потом всё более длинные, чтобы к моменту расчёта [i, j] все его подотрезки были готовы. Поэтому внешний цикл — по длине отрезка.

Классика: умножение цепочки матриц

Даны размеры матриц, которые надо перемножить: матрица k имеет размер p[k] × p[k+1]. Умножение матриц ассоциативно (результат не зависит от расстановки скобок), но число операций зависит! Перемножение матриц a×b и b×c стоит a·b·c скалярных умножений. Задача: расставить скобки так, чтобы суммарное число умножений было минимальным.

p = [10, 20, 30, 40]   # 3 матрицы: 10x20, 20x30, 30x40
n = len(p) - 1         # число матриц

# dp[i][j] — мин. число умножений для перемножения матриц i..j
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):              # длина отрезка: от 2 матриц
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = float("inf")
        for k in range(i, j):               # точка разбиения
            cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
            dp[i][j] = min(dp[i][j], cost)
print("Мин. число умножений:", dp[0][n - 1])

Разберём переход. Для отрезка матриц [i, j] мы выбираем, где поставить «последнее» умножение — после матрицы k. Тогда стоимость = (умножить левую группу) + (умножить правую группу) + (умножить две получившиеся матрицы размеров p[i]×p[k+1] и p[k+1]×p[j+1]). Перебираем все k и берём минимум. Внешний цикл по length гарантирует, что подотрезки уже посчитаны. Сложность — O(n^3): три вложенных цикла.

Вывод:

Мин. число умножений: 18000

Разбор ответа

У нас 3 матрицы: A (10×20), B (20×30), C (30×40). Два способа: (AB)C = 10·20·30 + 10·30·40 = 6000 + 12000 = 18000; A(BC) = 20·30·40 + 10·20·40 = 24000 + 8000 = 32000. Минимум — 18000, то есть выгоднее сначала перемножить A и B. ДП нашло это, перебрав обе расстановки скобок через точку разбиения.

Шаблон интервального ДП

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

для length от малой до n:
    для i (j = i + length - 1):
        для k от i до j-1:
            dp[i][j] = лучшее( dp[i][k] + dp[k+1][j] + стоимость_стыка )
ответ = dp[0][n-1]

Меняется только «стоимость стыка» и направление оптимизации (min/max). Например, в задаче «минимальная стоимость удаления палки разрезами» или «максимум очков за лопание шариков» — тот же каркас, другая формула стыка.

Сложность

Из-за O(n^3) интервальное ДП обычно применяют при n ≤ 500 (вспомни таблицу из урока об асимптотике: n^3 для 500 — это ~10^8). Существуют ускорения (оптимизация Кнута), снижающие до O(n^2) в особых случаях, но это продвинутая тема.

Подводные камни

• Порядок циклов. Обязательно внешний цикл — по длине отрезка; иначе будешь использовать ещё не посчитанные подзадачи.
• Границы k. Точка разбиения k идёт от i до j−1; легко ошибиться на единицу.
• Инициализация. База — отрезки длины 1 (часто dp[i][i] = 0); остальные — «бесконечность» для минимума.
• Кубическая сложность ограничивает n сотнями — проверяй по ограничениям, что пройдёшь.

Итог

• Интервальное ДП: состояние — отрезок [i, j], переход — перебор точки разбиения k.
• Внешний цикл идёт по длине отрезка, чтобы подотрезки были готовы заранее.
• Классика — оптимальная расстановка скобок (цепочка матриц) за O(n^3).
• Применимо при n в сотни; меняя «стоимость стыка», решаешь целый класс задач по одной канве.