Алгоритмы с нуля
Интервальная ДП: перемножение цепочки матриц и разбиение по последнему действию
Каждая ДП до сих пор имела состояние которое двигалось вдоль одного подвижного края: fib(n) уменьшает n, путь по сетке считает клетки до (row, col). Состояние этого урока захватывает целый срез входа и задаёт вопрос про него: “что лучшее ты можешь сделать на куске от индекса i до индекса j?” Это интервальная ДП, и у неё есть фирменный ход. Чтобы решить срез, ты угадываешь последнее решение принятое внутри него — где его разбить, или какой элемент обработать последним — пробуешь каждую догадку, и склеиваешь два меньших среза вместе. Поскольку каждый меньший срез уже должен быть решён, ты заполняешь таблицу по длине интервала, от коротких к длинным. Это форма стоящая за перемножением цепочки матриц и лопанием шариков (burst balloons) — две задачи которые выглядят невозможными пока не щёлкнет идея точки разбиения.
После этого урока ты можешь распознать интервальную ДП по её состоянию: dp[i][j] = лучший ответ для подинтервала [i..j] входа. Ты можешь написать ключевую рекурренту — dp[i][j] = лучшее по точке разбиения k из dp[слева] (склейка) dp[справа] + cost(i, k, j) — и объяснить почему ответ для среза строится из строго меньших срезов (оптимальная подструктура). Ты можешь реализовать перемножение цепочки матриц, которое минимизирует число скалярных умножений нужных чтобы перемножить цепочку матриц, с рекуррентой dp[i][j] = min по k из dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]. Ты понимаешь порядок перебора: цикл по длине интервала от короткой к длинной, потом по начальному индексу, так что каждый подсрез уже вычислен прежде чем он тебе понадобится. Ты знаешь сложность — O(n^3) время (n^2 состояний умножить на O(n) выборов разбиения), O(n^2) память. Наконец ты можешь сформулировать лопание шариков думая про последний шарик лопнутый внутри интервала — та же идея разбиения в другой шляпе. Это последний урок раздела; это также самая трудная форма ДП которую ты здесь встретишь.
Состояние это срез, не точка
В интервальной ДП состояние это непрерывный диапазон входа. Мы пишем dp[i][j] для лучшего ответа достижимого на элементах от индекса i до индекса j включительно — срез [i..j]. Одиночный элемент [i..i] это наименьший срез; полный массив [0..n-1] (или [1..n]) это цель. Всё между ними это подсрез.
Рекуррента: угадай последнее действие, разбей, склей
Ты не можешь решить срез напрямую, так ты угадываешь одно решение которое разбивает его на независимые куски. Обычно это решение это точка разбиения k: разрежь [i..j] на левую часть и правую часть, реши каждую, и добавь стоимость их соединения.
dp[i][j] = best over all valid split points k of:
dp[ left slice ] (combine) dp[ right slice ] + cost(i, k, j)Два подсреза строго короче чем [i..j], так они меньшие подзадачи. Это оптимальная подструктура которая делает ДП легальной: лучший ответ для всего среза составлен из лучших ответов для его частей. Ты пробуешь каждое разбиение k и держишь лучшее, потому что ты не знаешь заранее где оптимальный разрез.
Почему ты перебираешь по длине интервала
Вот часть на которой люди спотыкаются. Чтобы вычислить dp[i][j] ты читаешь значения dp для более коротких срезов. Так эти более короткие срезы уже должны быть заполнены. Чистый способ это гарантировать это цикл по длине интервала от короткой к длинной:
for length = 1, 2, 3, ... up to n: // outer: how big is the slice
for i = each valid start: // inner: where does it start
j = i + length - 1 // its end
fill dp[i][j] from already-done shorter slicesК тому времени как length достигает некоторого значения, каждый срез каждой меньшей длины готов. Цикл по i потом j напрямую читал бы клетки которые ещё не готовы. Длина-сначала это позвоночник корректности интервальной ДП.
Диагональный порядок заполнения
Представь таблицу ДП со строками i и столбцами j. Используется только верхний треугольник где i <= j. Перебор длина-сначала заполняет его диагональ за диагональю, начиная с главной диагонали (срезы длины 1) и двигаясь наружу к правому-верхнему углу (полный интервал):
j=1 j=2 j=3 j=4
i=1 0 -> 1 -> 2 -> 3 <- final answer at dp[1][4]
i=2 0 -> 1 -> 2
i=3 0 -> 1
i=4 0
(numbers = the diagonal / interval length - 1; arrows = fill order)Каждая клетка зависит только от клеток слева от неё (та же строка) и ниже неё (тот же столбец) — все из которых сидят на более ранних диагоналях.
Канонический пример: перемножение цепочки матриц
Ты хочешь перемножить матрицы A_1 * A_2 * ... * A_n. Умножение матриц ассоциативно — результат тот же как бы ты ни расставлял скобки — но стоимость нет. Умножение матрицы p x q на матрицу q x r стоит p*q*r скалярных умножений и производит матрицу p x r. Размерности цепочки хранятся в одном массиве p[0..n], где матрица A_i это p[i-1] x p[i].
Последнее умножение в любой расстановке скобок разбивает цепочку A_i..A_j на (A_i..A_k) и (A_k+1..A_j) для некоторого k. Левое произведение это p[i-1] x p[k], правое это p[k] x p[j], и их соединение стоит p[i-1]*p[k]*p[j]. Так:
dp[i][j] = min over k in [i, j-1] of
dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
dp[i][i] = 0 (a single matrix needs no multiplication)Разобрано на маленькой цепочке
Возьми размерности p = [40, 20, 30, 10, 30], т.е. четыре матрицы: A_1 это 40x20, A_2 это 20x30, A_3 это 30x10, A_4 это 10x30. Заполняй по длине:
length 2 (single split each):
dp[1][2] = 40*20*30 = 24000
dp[2][3] = 20*30*10 = 6000
dp[3][4] = 30*10*30 = 9000
length 3 (try each k):
dp[1][3] = min( k=1: 0+6000 +40*20*10=8000 -> 14000,
k=2: 24000+0 +40*30*10=12000 -> 36000 ) = 14000
dp[2][4] = min( k=2: 0+9000 +20*30*30=18000 -> 27000,
k=3: 6000+0 +20*10*30=6000 -> 12000 ) = 12000
length 4 (the whole chain):
dp[1][4] = min( k=1: 0+12000 +40*20*30=24000 -> 36000,
k=2: 24000+9000 +40*30*30=36000 -> 69000,
k=3: 14000+0 +40*10*30=12000 -> 26000 ) = 26000Минимум это 26000, достигнут разбиением в k=3: перемножь (A_1 A_2 A_3) сначала, потом на A_4. Наивный порядок слева-направо стоил бы больше. Точка разбиения это вся игра.
Перемножение цепочки матриц, длина-сначала
Размерности живут в p, матрицы A_1..A_n индексированы с 1. dp[i][j] это минимум скалярных умножений для подцепочки A_i..A_j. Заметь вложенность циклов: длина снаружи, начало i внутри, разбиение k в самой глубине.
1
function matrixChain(p) {
2
const n = p.length - 1; // number of matrices A_1..A_n
3
const dp = []; // dp[i][j] = min mults for A_i..A_j
4
for (let i = 0; i <= n; i++) dp.push(new Array(n + 1).fill(0));
5
6
// build by increasing chain length so sub-chains are ready
7
for (let len = 2; len <= n; len++) {
8
for (let i = 1; i <= n - len + 1; i++) {
9
const j = i + len - 1;
10
dp[i][j] = Infinity;
11
for (let k = i; k < j; k++) { // try every split A_i..A_k | A_k+1..A_j
12
const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
13
if (cost < dp[i][j]) dp[i][j] = cost;
14
}
15
}
16
}
17
return dp[1][n];
18
}
- L2 n матриц из массива размерностей длины n+1: A_i это p[i-1] x p[i].
- L4 dp[i][i] остаётся 0 - одиночная матрица не нуждается в умножении. Используется только i <= j.
- L7 Внешний цикл это ДЛИНА интервала, от короткой к длинной, так более короткие подцепочки уже решены.
- L8 Внутренний цикл это начальный индекс i; конец j вынужден i + len - 1.
- L10 Сброс на Infinity перед минимизацией по всем точкам разбиения.
- L11 Пробуй каждое разбиение k: левая цепочка A_i..A_k, правая цепочка A_k+1..A_j.
- L12 Стоимость = реши слева + реши справа + стоимость соединения p[i-1]*p[k]*p[j].
- L13 Держи самое дешёвое разбиение. dp[i][j] заканчивается как минимум по всем k.
Ключевой момент: более короткие срезы сначала, никогда не читай незаполненную клетку
Вся корректность этого кода держится на одном факте порядка: когда мы вычисляем dp[i][j], оба dp[i][k] и dp[k+1][j] покрывают строго более короткие цепочки, так внешний цикл длина-сначала уже заполнил их. Поменяй циклы местами чтобы перебирать i потом j напрямую и ты читал бы клетки которые всё ещё 0 (незаполнены), молча производя неправильные ответы.
Запуск на примере цепочки
Та же цепочка что в разборе: p = [40, 20, 30, 10, 30]. Ответ это 26000.
Наивный анализ предложил бы просто перемножать слева направо, но оптимальная расстановка скобок здесь сокращает работу пробуя каждое разбиение и держа минимум — ровно то что делает интервальная ДП.
Смотри как таблица заполняется диагональ за диагональю для p = [40, 20, 30, 10, 30]. Срезы длины 2 заполняются первыми (одно разбиение каждый), потом длины 3, потом вся цепочка. Каждый шаг показывает клетку которая записывается и текущий набор решённых клеток.
1
for (let len = 2; len <= n; len++) {
2
for (let i = 1; i <= n - len + 1; i++) {
3
const j = i + len - 1;
4
for (let k = i; k < j; k++)
5
cost = dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
6
}
7
}
Время: O(n^3)
Посчитай это из циклов, которые зеркалят структуру ДП точно:
- Есть O(n^2) состояний: одно
dp[i][j]на каждую паруi <= j(верхний треугольник таблицы n x n). - Заполнение каждого состояния пробует каждую точку разбиения k в диапазоне
[i, j-1], что до O(n) выборов, каждый O(1) работы.
Состояния умножить на работу-на-состояние = O(n^2) x O(n) = O(n^3). Три вложенных цикла — длина, начало, разбиение — это ровно эти три множителя. Для примера с 4 матрицами это крошечная константа; для n = 100 матриц это порядка миллиона операций, всё ещё мгновенно, но кубический рост важен по мере роста n.
Память: O(n^2)
Таблица хранит одно значение на состояние, и есть O(n^2) состояний (верхний треугольник). Это O(n^2) памяти. В отличие от линейных ДП (Фибоначчи, подъём по лестнице) ты не можешь сжать интервальную ДП до O(1) или O(n) строк, потому что вычисление одной клетки может тянуться назад ко многим более ранним диагоналям, не только к предыдущей строке — тебе нужен весь треугольник живым.
states work/state time space
linear DP O(n) O(1) O(n) O(n) or O(1)
2-D grid DP O(n^2) O(1) O(n^2) O(n^2) or O(n)
interval DP O(n^2) O(n) splits O(n^3) O(n^2) <- this lessonПочему длина-сначала обязательна, не выбор стиля
Рекуррента читает dp[i][k] и dp[k+1][j], оба покрывают более короткие интервалы чем [i..j]. Корректный порядок заполнения должен завершить все более короткие интервалы прежде любого более длинного. Перебор по возрастанию длины делает это автоматически: каждая клетка длины L зависит только от клеток длины < L, которые были закончены на более ранних проходах. Перебери наивно по i по возрастанию потом j по возрастанию и ты вычислял бы, скажем, dp[1][4] пока dp[2][4] (более далеко-тянущаяся зависимость на правой стороне той же строки) не закончена — читая устаревший 0 и возвращая неправильную, слишком-маленькую стоимость. Длина-сначала это единственный порядок который уважает зависимость, вот почему каждая интервальная ДП которую ты пишешь будет иметь length как свой внешний цикл.
Что представляет состояние dp[i][j] в интервальной ДП?
В рекурренте цепочки матриц dp[i][j] = min по k из dp[i][k] + dp[k+1][j] + cost, что это k?
Почему интервальная ДП должна перебирать по возрастанию длины интервала (длина это внешний цикл)?
Какая сложность по времени у цепочки матриц / интервальной ДП описанной здесь?
В лопании шариков, какое 'последнее действие' делает разбиение интервала чисто на независимые подинтервалы?
Умножение одиночной матрицы (подцепочка длины 1, dp[i][i]) стоит сколько скалярных умножений?
Для размерностей p = [40, 20, 30, 10, 30], чему равно dp[2][3] = p[1]*p[2]*p[3] (стоимость перемножить A_2 на A_3)?
Почему это работает
Почему “угадай последнее действие” работает. Интервальной ДП нужно чтобы срез разбивался на независимые куски. Приём в том чтобы зафиксировать одно решение которое делает разбиение и попробовать все его варианты. В цепочке матриц это решение это самое внешнее (последнее) умножение — выбор его точки разбиения k делает левую и правую подцепочки независимыми, каждая меньший интервал. В лопании шариков это последний шарик лопнутый внутри интервала — раз он последний, остаток интервала уже пуст, так его соседи это фиксированные границы. Оба это одна и та же идея: назови финальное действие, и оставшаяся задача чисто делится пополам на два интервала которые ты уже решил.
Частая ошибка
Ошибка: перебор по началу/концу вместо по длине. Самый частый баг интервальной ДП это цикл for i ... for j ... и вычисление dp[i][j] прежде чем все более короткие срезы готовы. Код запускается без падения — он просто читает клетки которые всё ещё на своём начальном 0 и возвращает неправильный (обычно слишком-маленький) ответ. Всегда делай длину интервала внешним циклом, потом выводи j = i + len - 1. Если ты когда-нибудь видишь интервальную ДП чей внешний цикл это начальный индекс, подозревай баг зависимости.
Граничные случаи
Ошибка на единицу в массиве размерностей. Цепочка матриц использует p длины n+1 для n матриц, где A_i это p[i-1] x p[i]. Стоимость соединения p[i-1]*p[k]*p[j] смешивает три разных индекса, и легко съехать на один. Проверь здравым смыслом на цепочке длины 2: dp[i][i+1] должно равняться p[i-1]*p[i]*p[i+1], единственный способ перемножить две матрицы. Базовый случай dp[i][i] = 0 (одиночная матрица) и требование i <= j (только верхний треугольник осмыслен) дополняют края.
Ещё практика
Лопание шариков, оформленное как интервальная ДП по последнему действию. У тебя есть шарики со значениями; лопание шарика i приносит nums[left]*nums[i]*nums[right] где left/right это его текущие соседи, потом он удаляется. Максимизируй итоговые монеты. Дополни массив виртуальными 1 на обоих концах. Пусть dp[i][j] = макс монет от лопания каждого шарика строго между границами i и j. Угадай k как последний шарик лопнутый в этом открытом интервале: когда он лопается, i и j это его соседи, так его награда это nums[i]*nums[k]*nums[j], и два подинтервала (i, k) и (k, j) независимы: dp[i][j] = max по k из dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]. Заполняй по длине интервала, тот же O(n^3). Заметь что это “последнее действие”, не “точка разбиения” — но механизм идентичен.
Объясни что это интервальная ДП, её рекурренту, почему она перебирает по длине интервала, пример цепочки матриц, и её сложность.
Интервальная ДП имеет состояние которое это срез входа: dp[i][j] = лучший ответ для подинтервала [i..j].
Рекуррента: угадай последнее решение внутри среза — точку разбиения k (или последний обработанный элемент) — которое разбивает его на два строго более коротких, независимых подинтервала, потом склей и добавь стоимость соединения:
dp[i][j] = best over k of dp[left] (combine) dp[right] + cost(i, k, j)Порядок перебора: цикл по длине интервала от короткой к длинной, потом по начальному индексу, потом по точке разбиения. Длина-сначала обязательна потому что каждая клетка читает только более короткие срезы, которые должны быть уже заполнены.
Перемножение цепочки матриц (канонический случай): минимизируй скалярные умножения для A_1..A_n, где A_i это p[i-1] x p[i]:
dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
dp[i][i] = 0Лопание шариков это та же форма с подвохом: вместо точки разбиения, угадай последний шарик лопнутый в интервале — раз он последний, его соседи это фиксированные границы интервала и две стороны независимы.
Сложность: O(n^2) состояний умножить на O(n) точек разбиения каждое = O(n^3) время, O(n^2) память.
Это закрывает раздел динамического программирования. Ты поднялся от одного подвижного индекса (Фибоначчи) к 2-D сетке к срезу входа с внутренним циклом разбиения — полный диапазон форм состояния ДП к которому тянется старший инженер.