Динамика по отрезкам: перемножение матриц, Burst Balloons и разрезание палки
ДП по отрезкам (interval DP) простыми словами: состояние dp[i][j], перебор точки разреза, правильный порядок обхода. Разбор цепочки матриц, Burst Balloons и Minimum Cost to Cut a Stick на Python.
Коротко
| Параметр | Значение |
|---|---|
| Состояние | dp[i][j] — ответ для подотрезка [i, j] |
| Переход | перебор точки k внутри отрезка: dp[i][k] и dp[k][j] (или k+1) |
| Порядок обхода | по возрастанию длины отрезка или i справа налево |
| Типичная сложность | по времени, по памяти |
| Когда применять | n до 300–500, ответ складывается из двух независимых половин |
Главная мысль: если задача про последовательность, где на каждом шаге что-то «склеивается», «лопается» или «режется», и результат шага зависит только от границ текущего куска, — почти наверняка это динамика по отрезкам.
Как узнать задачу на ДП по отрезкам
Обычная одномерная динамика идёт слева направо: dp[i] зависит от dp[i-1], dp[i-2] и так далее. Так решаются Climbing Stairs и House Robber. Но бывают задачи, где разумного «префикса» нет: операции происходят в середине массива, и после них соседи меняются.
Признаки interval DP:
- Входные данные — массив или строка, и операция затрагивает соседние элементы.
- Нужно выбрать порядок действий (какие матрицы перемножить первыми, какой шарик лопнуть, где резать), а перебор порядков даёт .
- После выбора одного действия задача распадается на левую и правую части, которые решаются независимо.
- Ограничения небольшие: n ≤ 100–500. Это прямой намёк на .
Шаблон почти всегда один и тот же:
Вместо минимума может быть максимум, вместо k+1 — k (если граница общая). Вся сложность задачи — понять, что именно означает k и что такое cost.
Разминка: самая длинная подпоследовательность-палиндром
Начнём с задачи, где перебора k ещё нет, зато хорошо видна структура. Дана строка s, найти длину самой длинной подпоследовательности, которая читается одинаково в обе стороны (LeetCode 516, Longest Palindromic Subsequence).
dp[i][j] — ответ для подстроки s[i..j]. Смотрим на крайние символы:
- если
s[i] == s[j], они оба войдут в палиндром:dp[i][j] = dp[i+1][j-1] + 2; - иначе один из краёв лишний:
dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
def longest_palindrome_subseq(s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return dp[0][n - 1] print(longest_palindrome_subseq('bbbab')) # 4 print(longest_palindrome_subseq('cbbd')) # 2
Обратите внимание на цикл for i in range(n - 1, -1, -1). Ячейка dp[i][j] читает dp[i+1][...], то есть строку ниже. Значит, строки надо заполнять снизу вверх. К порядку обхода мы ещё вернёмся — это главный источник багов в таких задачах.
Задача родственна наибольшей общей подпоследовательности: длина LPS строки равна LCS этой строки и её разворота. Но решение через отрезки естественнее и легко обобщается.
Классика: перемножение цепочки матриц
Исторически с этой задачи interval DP и начинается, её разбирают в учебнике Кормена.
Есть матрицы , размер — dims[i-1] × dims[i]. Умножение p × q на q × r стоит скалярных умножений. Результат не зависит от расстановки скобок (умножение ассоциативно), а стоимость — зависит, и сильно.
Пример: dims = [10, 30, 5, 60], то есть — 10×30, — 30×5, — 5×60.
- : .
- : .
Разница в шесть раз на трёх матрицах. Число способов расставить скобки растёт как числа Каталана, то есть экспоненциально, так что перебором не обойтись.
Наивная рекурсия
Ключевое наблюдение: у любой расстановки скобок есть последнее умножение. Оно делит цепочку на . Левая часть даёт матрицу dims[i] × dims[k+1], правая — dims[k+1] × dims[j+1] (индексы с нуля). Последнее умножение стоит dims[i] * dims[k+1] * dims[j+1].
def chain_naive(dims: list[int], i: int, j: int) -> int: if i == j: return 0 return min( chain_naive(dims, i, k) + chain_naive(dims, k + 1, j) + dims[i] * dims[k + 1] * dims[j + 1] for k in range(i, j) )
Это экспонента: одни и те же отрезки (i, j) считаются заново много раз. Различных отрезков всего , поэтому достаточно их запомнить.
Мемоизация
Самый быстрый путь к рабочему решению на собеседовании — добавить кэш. Подробнее о приёме — в статье про мемоизацию.
from functools import lru_cache def matrix_chain_memo(dims: list[int]) -> int: @lru_cache(maxsize=None) def solve(i: int, j: int) -> int: if i == j: return 0 return min( solve(i, k) + solve(k + 1, j) + dims[i] * dims[k + 1] * dims[j + 1] for k in range(i, j) ) return solve(0, len(dims) - 2) print(matrix_chain_memo([10, 30, 5, 60])) # 4500
Состояний , на каждое — работы, итого . Минус — глубина рекурсии до n, в Python при n около 1000 нужен sys.setrecursionlimit. Но при таких n и сам уже медленный.
Итеративно, с восстановлением ответа
Снизу вверх отрезки перебираются по длине: сначала все отрезки длины 2, потом 3 и так далее. Когда мы считаем отрезок длины L, все его части короче L и уже готовы.
Заодно сохраним, где был оптимальный разрез, чтобы вывести расстановку скобок — частый follow-up.
def matrix_chain(dims: list[int]) -> tuple[int, str]: n = len(dims) - 1 # число матриц dp = [[0] * n for _ in range(n)] split = [[0] * n for _ in range(n)] for length in range(2, n + 1): 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] + dims[i] * dims[k + 1] * dims[j + 1] if cost < dp[i][j]: dp[i][j] = cost split[i][j] = k def build(i: int, j: int) -> str: if i == j: return f'A{i + 1}' k = split[i][j] return f'({build(i, k)} {build(k + 1, j)})' return dp[0][n - 1], build(0, n - 1) print(matrix_chain([10, 30, 5, 60])) # (4500, '((A1 A2) A3)') print(matrix_chain([40, 20, 30, 10, 30])) # (26000, '((A1 (A2 A3)) A4)')
Таблица split — стандартный способ восстановить решение в любой динамике: храним не только значение, но и выбор, на котором оно достигнуто.
Burst Balloons: думать о последнем действии
LeetCode 312, уровень Hard. Есть шарики с числами nums. Лопая шарик i, получаем nums[left] * nums[i] * nums[right] монет, где left и right — его текущие соседи. За краями массива считаем шарики с единицей. Найти максимум монет.
Пример: [3, 1, 5, 8] → 167. Порядок: лопаем 1 (3·1·5 = 15), потом 5 (3·5·8 = 120), потом 3 (1·3·8 = 24), потом 8 (1·8·1 = 8).
Почему «первый шарик» не работает
Естественная мысль — перебрать, какой шарик лопнуть первым. Но после этого его соседи становятся соседями друг другу, и левая с правой частью перестают быть независимыми: стоимость лопания крайнего левого шарика правой части зависит от того, что осталось слева. Разбиения на две подзадачи не получается.
Переворачиваем: какой шарик лопнет последним
Возьмём отрезок между двумя «стенками» left и right (сами стенки не лопаем). Пусть k — шарик, который в этом отрезке лопнет последним. Тогда:
- пока он жив, он отделяет левую часть
(left, k)от правой(k, right)— они действительно независимы; - в момент, когда лопается
k, его соседи — ровноleftиright, потому что всё между ними уже лопнуто.
Здесь dp[l][r] — максимум монет, если лопнуть все шарики строго между l и r. Чтобы не возиться с краями, добавим по единице с двух сторон.
def max_coins(nums: list[int]) -> int: a = [1] + nums + [1] n = len(a) dp = [[0] * n for _ in range(n)] for length in range(2, n): # расстояние между стенками for left in range(n - length): right = left + length for k in range(left + 1, right): dp[left][right] = max( dp[left][right], dp[left][k] + dp[k][right] + a[left] * a[k] * a[right], ) return dp[0][n - 1] print(max_coins([3, 1, 5, 8])) # 167 print(max_coins([1, 5])) # 10
Сложность , на LeetCode n ≤ 300 — около 4,5 миллиона итераций внутреннего цикла, Python укладывается.
Приём «смотреть на последнее действие, а не на первое» — самое важное, что стоит вынести из этой задачи. Он же работает в задаче про цепочку матриц (последнее умножение) и в разрезании палки (первый разрез здесь эквивалентен «последней склейке» в обратном времени).
Minimum Cost to Cut a Stick
LeetCode 1547. Палка длины n, в массиве cuts — позиции, где её надо разрезать. Каждый разрез стоит столько, какова длина куска, который режем. Порядок разрезов выбираем сами. Найти минимальную суммарную стоимость.
Пример: n = 7, cuts = [1, 3, 4, 5] → 16.
Здесь важно, по чему строить отрезки. Длина палки может быть до , а разрезов — до 100. Поэтому индексы dp — это номера разрезов, а не координаты. Отсортируем разрезы и добавим концы палки:
c = [0, 1, 3, 4, 5, 7]
dp[i][j] — минимальная стоимость сделать все разрезы строго между c[i] и c[j]. Если первым режем в точке c[k], платим длину куска c[j] - c[i], и задача распадается на (i, k) и (k, j):
def min_cost(n: int, cuts: list[int]) -> int: c = [0] + sorted(cuts) + [n] m = len(c) dp = [[0] * m for _ in range(m)] for length in range(2, m): for i in range(m - length): j = i + length dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i + 1, j)) + c[j] - c[i] return dp[0][m - 1] print(min_cost(7, [1, 3, 4, 5])) # 16 print(min_cost(9, [5, 6, 1, 4, 2])) # 22
Слагаемое c[j] - c[i] не зависит от k, поэтому его можно вынести за минимум. Сложность , где m — число разрезов плюс два.
Заметьте сходство с Burst Balloons: обе задачи используют общие границы dp[i][k] + dp[k][j], а не dp[i][k] + dp[k+1][j], как в цепочке матриц. Разница в том, принадлежит ли точка k обеим половинам. Это стоит проговорить вслух на собеседовании, прежде чем писать код.
Слияние камней и префиксные суммы
Ещё одна классика той же формы: камни лежат в ряд, за одно действие сливаем две соседние кучки, платим их суммарный вес. Найти минимальную стоимость слить всё в одну кучку.
Последнее слияние объединяет [i..k] и [k+1..j] и стоит сумму всего отрезка — её берём из префиксных сумм за :
def merge_stones(stones: list[int]) -> int: n = len(stones) pre = [0] for x in stones: pre.append(pre[-1] + x) dp = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = min(dp[i][k] + dp[k + 1][j] for k in range(i, j)) + pre[j + 1] - pre[i] return dp[0][n - 1] print(merge_stones([3, 4, 1, 2])) # 20
На LeetCode есть усложнённая версия — 1000. Minimum Cost to Merge Stones, где сливаются ровно K соседних кучек. Там к состоянию добавляется третье измерение «на сколько кучек разбит отрезок», но каркас тот же.
Порядок обхода: самое важное и самое ломкое
В interval DP ячейка dp[i][j] зависит от ячеек внутри отрезка [i, j]. Если заполнить таблицу в неправильном порядке, вы прочитаете ещё не посчитанный ноль, и программа тихо вернёт неверный ответ без всяких ошибок.
Два корректных порядка:
1. По длине отрезка. Внешний цикл — длина, внутренний — левая граница. Все подотрезки строго короче, значит, уже посчитаны. Это самый надёжный вариант, его легко объяснить интервьюеру.
for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 ...
2. Левая граница справа налево, правая — слева направо. dp[i][j] зависит от dp[i][k] (та же строка, левее — уже есть, ведь j растёт) и dp[k+1][j] (строки ниже — уже есть, ведь i убывает).
for i in range(n - 1, -1, -1): for j in range(i + 1, n): ...
А вот так — нельзя:
for i in range(n): # ОШИБКА: i растёт for j in range(i + 1, n): # dp[k + 1][j] для k >= i ещё не посчитан ...
Если сомневаетесь, нарисуйте таблицу и стрелки зависимостей для одной ячейки. Для interval DP заполняется только верхний треугольник i ≤ j, а зависимости смотрят влево и вниз. Мемоизация сверху вниз снимает этот вопрос совсем: рекурсия сама посчитает то, что нужно, в нужном порядке. Поэтому на собеседовании разумно начать с неё, а потом, если спросят, переписать итеративно.
Сложность и оптимизации
Базовая оценка: состояний × вариантов k = времени, памяти. При n = 500 это 125 миллионов операций в худшем случае — на C++ терпимо, на Python уже долго. Практический ориентир для Python — n до 200–300.
Оптимизация Кнута. Для некоторых задач (слияние камней, оптимальное дерево поиска) оптимальная точка разреза монотонна: opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]. Тогда k можно перебирать только в этом диапазоне, и суммарная работа падает до . Условие выполняется, когда функция стоимости удовлетворяет неравенству четырёхугольника и монотонна по вложению отрезков. Сумма отрезка, как в слиянии камней, этим условиям удовлетворяет. На обычном собеседовании до этого доходят редко, но упомянуть — плюс.
def merge_stones_knuth(stones: list[int]) -> int: n = len(stones) pre = [0] for x in stones: pre.append(pre[-1] + x) dp = [[0] * n for _ in range(n)] opt = [[i] * n for i in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = float('inf') for k in range(opt[i][j - 1], min(opt[i + 1][j], j - 1) + 1): value = dp[i][k] + dp[k + 1][j] if value < dp[i][j]: dp[i][j] = value opt[i][j] = k dp[i][j] += pre[j + 1] - pre[i] return dp[0][n - 1]
Для Burst Balloons и цепочки матриц в общем виде такая монотонность не гарантирована, там честный . Для цепочки матриц существует алгоритм Ху — Шинга за , но его на собеседованиях не спрашивают.
Типичные ошибки
- Неправильный порядок обхода. Самая частая. Таблица заполняется, ответ получается, но неверный. Лечится обходом по длине или мемоизацией.
- Перепутаны
kиk+1. Принадлежит ли точка разреза обеим частям (общая граница, как в Burst Balloons и разрезании палки) или ровно одной (как в цепочке матриц)? Решите это до кода. - Перебор первого действия вместо последнего. В Burst Balloons это ломает независимость половин. Если подзадачи «слипаются», попробуйте перевернуть время.
- Индексы по координатам вместо номеров точек. В задаче про палку
nдо миллиона: таблицаn × nне влезет в память. Состояние строится по разрезам. - Забытые стенки. Добавление единиц по краям в Burst Balloons и концов
0иnв задаче про палку убирает целый класс проверок на границы. - Бесконечность как начальное значение. Для минимума инициализируйте
float('inf')только там, где есть хотя бы один вариантk, иначе отрезки длины 1 получат бесконечность вместо нуля.
Где встречается на собеседованиях
Interval DP — уровень Medium/Hard. На скрининге его дают редко, а на финальных секциях Burst Balloons и похожие задачи дают, чтобы проверить, умеете ли вы найти правильное состояние, а не вспомнить формулу.
Задачи для тренировки, по возрастанию сложности:
| Задача | Номер LeetCode | Что тренирует |
|---|---|---|
| Longest Palindromic Subsequence | 516 | базовая структура dp[i][j] |
| Palindromic Substrings | 647 | отрезки без перебора k |
| Minimum Score Triangulation of Polygon | 1039 | перебор k с общими границами |
| Minimum Cost to Cut a Stick | 1547 | состояние по точкам, а не координатам |
| Burst Balloons | 312 | «последнее действие» |
| Strange Printer | 664 | нетривиальное слияние отрезков |
| Minimum Cost to Merge Stones | 1000 | третье измерение в состоянии |
Как вести себя на интервью:
- Скажите, что перебор порядков даёт или числа Каталана, и что после выбора одного действия задача делится на две независимые части.
- Сформулируйте состояние словами: «
dp[i][j]— лучший ответ для отрезка отiдоj, где …». Половина успеха в этом «где». - Выпишите переход и базу. Проговорите, общая ли граница у половин.
- Напишите мемоизацию — она короче и не требует думать о порядке.
- Оцените и сверьте с ограничениями.
Если хочется освежить базу, начните со статьи динамическое программирование для начинающих. Соседние разновидности динамики — ДП на деревьях и ДП по подмножествам. А задачи про пересечение и слияние интервалов (Merge Intervals, Meeting Rooms) — это совсем другая техника, они разобраны в статье задачи на интервалы.