Шаблон интервального DP и порядок заполнения

DP по интервалам — это шаблон динамического программирования, в котором состояние dp[i][j] представляет оптимальный ответ для подзадачи, охватывающей индексы i–j. Основная идея заключается в том, что сначала решаются меньшие интервалы, а затем постепенно строится решение для всего диапазона. Этот шаблон естественным образом описывает такие задачи, как умножение цепочки матриц, разбиение на палиндромы и лопание шаров, где границами подзадачи являются левый и правый концы диапазона.

В DP по интервалам состоянием является dp[i][j], где i <= j. Базовые случаи — это интервалы из одного элемента: dp[i][i]. Они решаются очевидным образом — например, для одной матрицы стоимость умножения равна нулю. Для интервалов из двух элементов dp[i][i+1] также часто существуют простые решения. Мы заполняем таблицу для интервалов возрастающей длины, начиная с длины 1 и заканчивая n.

Ключевая деталь DP по интервалам — это порядок заполнения. Необходимо вычислить все интервалы длины L до вычисления интервалов длины L+1, поскольку более длинный интервал зависит от более коротких подинтервалов. Внешний цикл перебирает длину интервала от 2 до n, средний цикл задаёт левую границу i, а правую границу мы вычисляем как j = i + L - 1.

Классическая задача на DP по интервалам — умножение цепочки матриц: по заданным матрицам с размерами dims[0..n] найдите минимальное число скалярных умножений, необходимое для вычисления произведения. Умножение матрицы A(p×q) на B(q×r) требует p*q*r операций. dp[i][j] = минимальная стоимость умножения матриц от i до j. Точка разделения k определяет, где последовательность разделяется на две подцепочки.

Разберём пример с цепочкой матриц с размерами [10, 30, 5, 60], представляющих три матрицы: A(10×30), B(30×5), C(5×60). Для dp[0][2] проверим разделение в точке k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, а также в точке k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Таким образом, dp[0][2] = 4500; этот результат достигается, если сначала перемножить AB.

При вычислении dp[i][j] мы обращаемся к dp[i][k] и dp[k+1][j] для всех k из [i, j-1]. Оба подинтервала имеют строго меньшую длину, чем [i, j]. Если перебирать длину от меньшей к большей, все необходимые подинтервалы будут вычислены до того, как понадобятся. Это основное доказательство корректности порядка заполнения DP по интервалам: более короткие интервалы всегда являются зависимостями более длинных.

Кроме того, DP по интервалам можно реализовать сверху вниз с мемоизацией. Мы пишем рекурсивную функцию solve(i, j), которая возвращает оптимальную стоимость для интервала [i, j], и сохраняем результаты в словаре. Порядок заполнения автоматически обрабатывается рекурсией. Подход сверху вниз часто проще для понимания, но может иметь накладные расходы на вызовы функций; подход снизу вверх на практике работает быстрее для больших входных данных.

DP по интервалам имеет O(n²) состояний — все пары (i, j) — и каждое состояние перебирает O(n) точек разделения, что в сумме даёт время O(n³). Для таблицы DP требуется память O(n²). Для умножения цепочки из 100 матриц это 1 000 000 операций — вполне приемлемый объём. Этот шаблон встречается во многих сложных задачах LeetCode и часто используется на собеседованиях FAANG благодаря своей неочевидной структуре.

Чтобы восстановить фактическую расстановку скобок, а не только стоимость, храните отдельную таблицу split[i][j], в которой для каждого состояния записывается значение k, достигшее минимума. Затем рекурсивно считайте точки разделения: reconstruct(i, j) выводит оптимальную группировку, рекурсивно обрабатывая [i, split[i][j]] и [split[i][j]+1, j]. Этот метод применим ко всем задачам на DP по интервалам.

Универсальный шаблон DP по интервалам состоит из трёх частей: (1) инициализировать базовые случаи для отдельных элементов, (2) перебирать возрастающие длины и для каждой длины перебирать допустимые левые границы, вычисляя правую границу, и (3) для каждого интервала перебирать все точки разделения и применять рекуррентное соотношение, зависящее от задачи. Между задачами меняется только формула рекуррентного соотношения во внутреннем цикле.

DP по интервалам используется в таких задачах, как: Умножение цепочки матриц (минимизация числа операций), Взрывание шаров (максимизация количества монет), Странный принтер (минимизация операций печати), Триангуляция многоугольника с минимальной стоимостью и Разбиение на палиндромы II. В каждой используется один и тот же каркас порядка заполнения, но разные рекуррентные соотношения. Распознавайте этот шаблон, когда задача требует найти оптимальное значение для диапазона или последовательности, которую можно разделить в любой внутренней точке.

Проверьте своё понимание понятий из курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию», рассмотренных в этом уроке.

В этом уроке Вы узнали, что DP по интервалам использует dp[i][j] для представления оптимального ответа на диапазоне, порядок заполнения должен следовать возрастающей длине интервалов, чтобы подинтервалы вычислялись первыми, а универсальный шаблон требует времени O(n³) и памяти O(n²). Далее мы рассмотрим самую длинную палиндромную подпоследовательность и подстроку, используя этот же шаблон.