Оптимизация Кнута: интервальное ДП за O(n²) вместо O(n³)

Оптимизация Кнута для ДП по отрезкам: условие opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j], почему выходит O(n²), слияние кучек, разрезание палки и оптимальное дерево поиска на Python.

9 мин чтенияалгоритмы · динамическое программирование · оптимизация · python

Коротко

ЧтоСуть
Вид переходаdp[i][j]=min⁡i<r<j(dp[i][r]+dp[r][j])+w(i,j)dp[i][j] = \min_{i < r < j} \big(dp[i][r] + dp[r][j]\big) + w(i, j), ww не зависит от rr
Ключевое условиеopt[i][j−1]≤opt[i][j]≤opt[i+1][j]opt[i][j-1] \le opt[i][j] \le opt[i+1][j]
Когда оно верноww удовлетворяет неравенству четырёхугольника и монотонна по вложению отрезков
Было → сталоO(n3)→O(n2)O(n^3) \to O(n^2) по времени, память O(n2)O(n^2)
Классические задачислияние кучек (линейное и по кругу), разрезание палки, оптимальное дерево поиска
  • Идея в одну строку: перебирать точку разреза не на всём отрезке, а только между оптимумами двух соседних, уже посчитанных отрезков.
  • Почему O(n2)O(n^2): для каждой длины отрезка длины окон телескопически складываются в O(n)O(n).
  • Главная ловушка: если стоимость зависит от точки разреза (цепочка матриц, Burst Balloons), приём молча даёт неверный ответ.

Сама динамика по отрезкам — порядок обхода, состояние dp[i][j]dp[i][j], разбор цепочки матриц и Burst Balloons — есть в статье про ДП по отрезкам. Родственный приём для задач «разбей массив на k групп» и общая теория монотонности оптимума — в статье про оптимизацию «разделяй и властвуй». Здесь — только Кнут на отрезках, но подробно: откуда берётся окно, как не ошибиться с границами и где приём применять нельзя.

Шаблон, который распознаёт оптимизация

Оптимизация Кнута работает с переходом строго определённой формы. Удобнее всего писать его на полуинтервалах [i,j)[i, j):

dp[i][j]=min⁡i<r<j(dp[i][r]+dp[r][j])+w(i,j),dp[i][i+1]=0dp[i][j] = \min_{i < r < j} \big( dp[i][r] + dp[r][j] \big) + w(i, j), \qquad dp[i][i+1] = 0

Отрезок режется точкой rr на две части, решения частей складываются, и сверху добавляется стоимость w(i,j)w(i, j), которая зависит только от концов отрезка. Обозначим opt[i][j]opt[i][j] — точку rr, на которой достигается минимум.

Наивное решение перебирает rr по всему отрезку: O(n2)O(n^2) состояний по O(n)O(n) вариантов, итого O(n3)O(n^3). При n=400n = 400 на Python это около 10 миллионов итераций внутреннего цикла и 2 секунды — уже на грани лимитов. При n=2000n = 2000 наивный вариант безнадёжен даже на C++.

Оптимизация Кнута говорит: если выполнено

opt[i][j−1]≤opt[i][j]≤opt[i+1][j],opt[i][j-1] \le opt[i][j] \le opt[i+1][j],

то rr достаточно перебирать только в этом окне. Оба края окна уже посчитаны: отрезки [i,j−1)[i, j-1) и [i+1,j)[i+1, j) на единицу короче, а мы идём по возрастанию длины.

Интуиция у условия простая. Добавили элемент справа — точка разреза не уедет влево. Убрали элемент слева — тоже не уедет влево. Оптимальный разрез «следует» за отрезком.

Почему окно правильное

Достаточное условие — функция ww удовлетворяет двум свойствам при a≤b≤c≤da \le b \le c \le d:

  1. Неравенство четырёхугольника: w(a,c)+w(b,d)≤w(a,d)+w(b,c)w(a, c) + w(b, d) \le w(a, d) + w(b, c).
  2. Монотонность по вложению: w(b,c)≤w(a,d)w(b, c) \le w(a, d) — объемлющий отрезок не дешевле вложенного.

Сумма на отрезке неотрицательных чисел удовлетворяет обоим: в первом неравенстве обе части равны, а второе следует из неотрицательности. Именно такая стоимость стоит в слиянии кучек, разрезании палки и задаче об оптимальном дереве.

Дальше доказательство идёт в два шага. Первый шаг — лемма Яо: если ww обладает обоими свойствами, то и сама dpdp удовлетворяет неравенству четырёхугольника. Доказывается индукцией по длине отрезка, и это самая техническая часть — её можно принять на веру.

Второй шаг короткий, и его полезно понимать, потому что он объясняет, откуда берётся окно. Обозначим fj(r)=dp[i][r]+dp[r][j]f_j(r) = dp[i][r] + dp[r][j] — значение, которое даёт разрез rr для отрезка [i,j)[i, j). Возьмём два разреза r<r′r < r' и применим неравенство четырёхугольника для dpdp к точкам r≤r′≤j−1≤jr \le r' \le j-1 \le j:

dp[r][j−1]+dp[r′][j]≤dp[r][j]+dp[r′][j−1].dp[r][j-1] + dp[r'][j] \le dp[r][j] + dp[r'][j-1].

Прибавим к обеим частям dp[i][r]+dp[i][r′]dp[i][r] + dp[i][r'] и перегруппируем:

fj(r′)−fj(r)≤fj−1(r′)−fj−1(r).f_j(r') - f_j(r) \le f_{j-1}(r') - f_{j-1}(r).

Смысл: если правый разрез r′r' был не хуже левого rr на отрезке [i,j−1)[i, j-1), то на отрезке [i,j)[i, j) он тоже не хуже. Значит, всё, что левее opt[i][j−1]opt[i][j-1], проигрывало ему раньше и проигрывает теперь — искать там бессмысленно. Это левая граница окна. Правая доказывается зеркально.

На практике доказательство пишут редко. Гораздо чаще проверяют гипотезу стресс-тестом: наивное ДП против оптимизированного на тысячах случайных маленьких входов. Ровно так проверен весь код ниже.

Почему получается O(n²)

Зафиксируем длину отрезка LL. Для отрезка [i,i+L)[i, i+L) окно имеет длину opt[i+1][i+L]−opt[i][i+L−1]+1opt[i+1][i+L] - opt[i][i+L-1] + 1. Сложим по всем ii:

∑i(opt[i+1][i+L]−opt[i][i+L−1]+1)=opt[n−L+1][n]−opt[0][L−1]+(n−L+1)≤2n.\sum_{i} \big(opt[i+1][i+L] - opt[i][i+L-1] + 1\big) = opt[n-L+1][n] - opt[0][L-1] + (n - L + 1) \le 2n.

Сумма телескопическая: правый край окна для ii — это левый край для i+1i+1, и почти всё сокращается. Каждая отдельная клетка может перебрать много вариантов, но в сумме по одной длине — не больше 2n2n. Длин nn, итого O(n2)O(n^2).

Замеры на слиянии кучек со случайными весами подтверждают оценку:

nитераций, наивноитераций, Кнутвремя, наивновремя, Кнут
100166 6509 7420.024 с0.002 с
2001 333 30040 2560.19 с0.016 с
40010 666 600158 3452.0 с0.035 с

При n=400n = 400 итераций почти ровно n2n^2, а при n=1000n = 1000 оптимизированная версия на Python укладывается примерно в полсекунды. Наивная там работала бы десятки секунд.

Слияние кучек

Классическая задача: в ряд лежат nn кучек камней. За ход можно слить две соседние кучки, стоимость хода — суммарное число камней в них. Нужно слить всё в одну кучку с минимальной стоимостью.

Последнее слияние объединяет кучки [i,r)[i, r) и [r,j)[r, j), и неважно, где именно rr, его стоимость — сумма всего отрезка. Поэтому w(i,j)=pre[j]−pre[i]w(i, j) = pre[j] - pre[i] через префиксные суммы, и переход ровно того вида, что нужен.

def merge_piles(a: list[int]) -> int: """Минимальная стоимость слить соседние кучки в одну (стоимость слияния = сумма).""" n = len(a) pre = [0] for x in a: pre.append(pre[-1] + x) # dp[i][j] — слить кучки a[i..j-1] (полуинтервал), opt[i][j] — лучший разрез dp = [[0] * (n + 1) for _ in range(n + 1)] opt = [[0] * (n + 1) for _ in range(n + 1)] for i in range(n): opt[i][i + 1] = i + 1 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length best, best_r = float('inf'), -1 lo = opt[i][j - 1] hi = min(opt[i + 1][j], j - 1) for r in range(lo, hi + 1): # вместо range(i + 1, j) value = dp[i][r] + dp[r][j] if value < best: best, best_r = value, r dp[i][j] = best + pre[j] - pre[i] opt[i][j] = best_r return dp[0][n] print(merge_piles([3, 1, 4, 1, 5])) # 32

Отличие от наивной версии — одна строка: range(lo, hi + 1) вместо range(i + 1, j). Всё остальное — обычная динамика по отрезкам.

Тонкое место — инициализация optopt для отрезков длины 1. Разреза у них нет, но значение нужно как граница окна для длины 2. Мы кладём opt[i][i + 1] = i + 1: тогда для отрезка [i,i+2)[i, i+2) левая граница i+1i+1 — единственный допустимый разрез. Правая граница opt[i + 1][i + 2] равна i+2i + 2, это уже за пределами отрезка, поэтому min(..., j - 1). Для длин от 3 и больше обрезка не срабатывает, но и не мешает.

Функция сверена с переборной рекурсией на 2000 случайных массивов длиной до 9.

Кучки по кругу

Если кучки лежат по кругу, первая и последняя тоже соседние. Стандартный приём — удвоить массив: b = a + a, посчитать динамику на отрезках длиной до nn и взять минимум по всем dp[i][i+n]dp[i][i+n]. Каждый такой отрезок — один из способов «разрезать» круг. Оптимизация Кнута переносится без изменений: удвоенный массив по-прежнему состоит из неотрицательных чисел.

def merge_piles_circle(a: list[int]) -> int: n = len(a) b = a + a pre = [0] for x in b: pre.append(pre[-1] + x) m = 2 * n dp = [[0] * (m + 1) for _ in range(m + 1)] opt = [[0] * (m + 1) for _ in range(m + 1)] for i in range(m): opt[i][i + 1] = i + 1 for length in range(2, n + 1): # длиннее n отрезки не нужны for i in range(m - length + 1): j = i + length best, best_r = float('inf'), -1 for r in range(opt[i][j - 1], min(opt[i + 1][j], j - 1) + 1): value = dp[i][r] + dp[r][j] if value < best: best, best_r = value, r dp[i][j] = best + pre[j] - pre[i] opt[i][j] = best_r return min(dp[i][i + n] for i in range(n)) print(merge_piles_circle([1, 8, 7, 1])) # 28, а в линию было бы 34

На [1, 8, 7, 1] выгодно сначала слить две единицы через «шов» круга: 22, потом 2+7=92 + 7 = 9, потом 9+8=179 + 8 = 17, итого 2828. В линию единицы не соседи, и лучшее, что получится, — 3434.

Разрезание палки (LeetCode 1547)

В задаче Minimum Cost to Cut a Stick палку длины nn надо разрезать в заданных точках, а стоимость каждого разреза равна длине куска, который режем в этот момент. В статье про ДП по отрезкам она решается за O(m3)O(m^3), где mm — число разрезов.

Добавим концы палки к точкам: x=[0,c1,…,cm,n]x = [0, c_1, \dots, c_m, n]. Первый разрез на куске между точками xix_i и xjx_j стоит xj−xix_j - x_i — независимо от того, где режем. Это снова стоимость «длина отрезка», она линейна и монотонна, условия Кнута выполнены:

def min_cost_cut(n: int, cuts: list[int]) -> int: x = [0] + sorted(cuts) + [n] m = len(x) # dp[i][j] — стоимость всех разрезов строго между точками x[i] и x[j] dp = [[0] * m for _ in range(m)] opt = [[0] * m for _ in range(m)] for i in range(m - 1): opt[i][i + 1] = i + 1 for length in range(2, m): for i in range(m - length): j = i + length best, best_k = float('inf'), -1 for k in range(opt[i][j - 1], min(opt[i + 1][j], j - 1) + 1): value = dp[i][k] + dp[k][j] if value < best: best, best_k = value, k dp[i][j] = best + x[j] - x[i] opt[i][j] = best_k return dp[0][m - 1] print(min_cost_cut(7, [1, 3, 4, 5])) # 16 print(min_cost_cut(9, [5, 6, 1, 4, 2])) # 22

По ограничениям LeetCode разрезов не больше 100, и кубическое решение проходит. Но если на собеседовании спросят «а если разрезов 10410^4?», это и есть правильный ответ: O(m2)O(m^2) через оптимизацию Кнута. Заметьте, что код почти дословно повторяет слияние кучек — это одна и та же задача, прочитанная в обратном направлении.

Оптимальное дерево поиска

Именно на этой задаче Дональд Кнут в 1971 году и придумал приём. Есть nn ключей в отсортированном порядке. Ключ kk ищут pkp_k раз, а между ключами k−1k-1 и kk ищут отсутствующие значения qkq_k раз (промахи; q0q_0 — левее всех ключей, qnq_n — правее). Нужно построить двоичное дерево поиска, в котором суммарная стоимость поиска минимальна: успешный поиск ключа на глубине dd стоит dd сравнений, промах в «пустом месте» под dd ключами стоит dd.

Если корень отрезка ключей [i,j)[i, j) — ключ rr, то слева дерево на [i,r)[i, r), справа на [r+1,j)[r+1, j), и все ключи и промахи отрезка опускаются на один уровень. Это добавляет их суммарный вес w(i,j)=∑k=ij−1pk+∑k=ijqkw(i, j) = \sum_{k=i}^{j-1} p_k + \sum_{k=i}^{j} q_k:

cost[i][j]=min⁡i≤r<j(cost[i][r]+cost[r+1][j])+w(i,j),cost[i][i]=0.cost[i][j] = \min_{i \le r < j} \big( cost[i][r] + cost[r+1][j] \big) + w(i, j), \qquad cost[i][i] = 0.

Форма чуть другая — корень rr выпадает из обеих частей, — но окно то же: root[i][j−1]≤root[i][j]≤root[i+1][j]root[i][j-1] \le root[i][j] \le root[i+1][j]. Это и есть исходная теорема Кнута.

def optimal_bst(p: list[int], q: list[int]): """p[k] — частота успешного поиска ключа k, q[k] — промахов между ключами k-1 и k. len(q) == len(p) + 1. Возвращает стоимость и корни для восстановления дерева.""" n = len(p) # w[i][j] — суммарный вес отрезка ключей [i, j) вместе с промахами q[i..j] w = [[0] * (n + 1) for _ in range(n + 1)] for i in range(n + 1): w[i][i] = q[i] for j in range(i + 1, n + 1): w[i][j] = w[i][j - 1] + p[j - 1] + q[j] cost = [[0] * (n + 1) for _ in range(n + 1)] root = [[0] * (n + 1) for _ in range(n + 1)] for i in range(n): cost[i][i + 1] = w[i][i + 1] root[i][i + 1] = i for length in range(2, n + 1): for i in range(n - length + 1): j = i + length best, best_r = float('inf'), -1 # корень — ключ r, слева ключи [i, r), справа [r + 1, j) for r in range(root[i][j - 1], root[i + 1][j] + 1): value = cost[i][r] + cost[r + 1][j] if value < best: best, best_r = value, r cost[i][j] = best + w[i][j] root[i][j] = best_r return cost[0][n], root def build(root, i, j): """Дерево как кортеж (левое, ключ, правое).""" if i == j: return None r = root[i][j] return (build(root, i, r), r, build(root, r + 1, j)) cost, root = optimal_bst([4, 2, 6, 3], [1, 0, 1, 0, 2]) print(cost) # 35 print(build(root, 0, 4)) # ((None, 0, (None, 1, None)), 2, (None, 3, None))

Здесь граница отрезков другая, и обрезка min(..., j - 1) не нужна: root[i][i + 1] = i уже допустимый корень, и окно для длины 2 — это [i,i+1][i, i+1], оба варианта законные.

Проверим ответ руками. Корень — ключ 2 (вес 6) на глубине 1, под ним ключи 0 и 3 на глубине 2, ключ 1 — на глубине 3. Успешные поиски: 6+2⋅4+2⋅3+3⋅2=266 + 2 \cdot 4 + 2 \cdot 3 + 3 \cdot 2 = 26. Промахи: q0=1q_0 = 1 под двумя ключами, q2=1q_2 = 1 под тремя, q4=2q_4 = 2 под двумя — 2+3+4=92 + 3 + 4 = 9. Итого 3535. Сверка с переборной рекурсией и пересчётом стоимости по восстановленному дереву — 2000 случайных тестов, все совпали.

Массив root — побочный продукт оптимизации, и его же используют для восстановления ответа. Отдельная таблица для восстановления не нужна.

Где приём не работает

Самая частая ошибка — применить окно к задаче, которая лишь похожа на шаблон.

Стоимость зависит от точки разреза. В перемножении цепочки матриц переход dp[i][j]=min⁡r(dp[i][r]+dp[r][j]+didrdj)dp[i][j] = \min_r (dp[i][r] + dp[r][j] + d_i d_r d_j): слагаемое didrdjd_i d_r d_j зависит от rr, и шаблон уже не тот. Пример: размерности [1, 9, 4, 8, 8] (матрицы 1×91 \times 9, 9×49 \times 4, 4×84 \times 8, 8×88 \times 8). Наивная динамика даёт 132132, и для полного отрезка оптимальный разрез opt[0][4]=3opt[0][4] = 3. При этом opt[1][4]=2opt[1][4] = 2 — правая граница окна меньше настоящего оптимума. Окно Кнута [2,2][2, 2] не видит правильный разрез и возвращает 324324. Burst Balloons ломается так же: там в стоимость входит значение шарика rr.

Стоимость не монотонна по вложению. Если в слиянии кучек разрешить отрицательные числа, неравенство четырёхугольника для суммы всё ещё выполняется (там равенство), а монотонность — нет. Стресс-тест на числах от −9 до 9 дал 933 расхождения на 3000 тестов. Минимальный пример: [-5, -5, 8, -7], верный ответ −21-21, с окном получается −18-18.

Слияние по KK кучек. В LeetCode 1000. Minimum Cost to Merge Stones сливают сразу KK соседних кучек, и состояние приходится расширять числом кучек на отрезке. Прямолинейно приложить окно Кнута к такой динамике нельзя — сначала нужна своя проверка монотонности.

Правило простое: перед тем как сужать перебор, проверьте, что ww не зависит от rr, неотрицательна по смыслу и растёт при расширении отрезка. Если сомневаетесь — напишите наивную версию и прогоните сравнение на случайных маленьких тестах. Это пять минут, а ошибка без проверки не проявится на примерах из условия.

Детали реализации

  • Порядок обхода. Нужно, чтобы opt[i][j−1]opt[i][j-1] и opt[i+1][j]opt[i+1][j] были посчитаны раньше opt[i][j]opt[i][j]. Обход по возрастанию длины это гарантирует. Подходит и обход «ii от n−1n-1 вниз, jj от i+1i+1 вверх» — оба соседа к моменту расчёта готовы.
  • Хранить нужно opt. Без таблицы оптимумов окно взять неоткуда. Память остаётся O(n2)O(n^2), как и у самой динамики.
  • Равные значения. Брать первый минимум (<) или последний (<=) — неважно, если делать это последовательно. Стресс-тест на массивах с числами 0–3, где ничьих очень много, совпал с наивной версией в обоих вариантах.
  • Пустое окно. Если из-за ошибки в границах lo > hi, цикл не выполнится, best останется бесконечностью, и ответ «испортится» молча. Полезно на время отладки вставить assert best_r != -1.
  • Полуинтервалы или отрезки. Для слияния кучек удобнее полуинтервалы [i,j)[i, j) с разрезом rr, общим для обеих частей. Для дерева поиска — корень, который не входит ни в одну часть. Смешивать конвенции в одном коде — верный способ получить off-by-one в окне.

Сложность

ВариантВремяПамять
Наивное ДП по отрезкамO(n3)O(n^3)O(n2)O(n^2)
С оптимизацией КнутаO(n2)O(n^2)O(n2)O(n^2)

Для слияния кучек в линию существуют и более быстрые алгоритмы — Ху–Таккера и Гарсиа–Уокса, за O(nlog⁡n)O(n \log n). Они заметно сложнее и на собеседованиях не встречаются, а олимпиадные ограничения обычно рассчитаны как раз на O(n2)O(n^2).

Типичные ошибки

  1. Окно без проверки условий. Цепочка матриц, Burst Balloons, кучки с отрицательными весами — примеры, где приём даёт неверный ответ без единой ошибки выполнения.
  2. Забыли инициализировать opt для коротких отрезков. Нули в opt[i][i + 1] дают окно, начинающееся левее отрезка, и разрез r≤ir \le i.
  3. Нет обрезки правой границы. В конвенции полуинтервалов opt[i + 1][i + 2] = i + 2 выходит за отрезок [i,i+2)[i, i+2) — без min(..., j - 1) получится разрез по краю.
  4. Посчитали opt, но не сохранили. Если записывать только dp[i][j], следующие отрезки берут окно из нулей.
  5. Путаница с O(n2)O(n^2). Отдельная клетка может перебрать Θ(n)\Theta(n) вариантов — оценка амортизированная, по всем клеткам одной длины. Пытаться доказать «окно всегда маленькое» бесполезно.

Где встречается на собеседованиях

На обычном интервью оптимизацию Кнута не требуют, но она хорошо работает как follow-up к задачам на ДП по отрезкам. Типичный сценарий: вы решили Minimum Cost to Cut a Stick или задачу о слиянии камней за O(n3)O(n^3), и интервьюер спрашивает, что делать при n=5000n = 5000. Ответ «оптимальная точка разреза монотонна, поэтому перебираем только между opt[i][j−1]opt[i][j-1] и opt[i+1][j]opt[i+1][j], итого O(n2)O(n^2)» плюс пара слов о том, почему стоимость здесь подходит, — сильный сигнал.

Чаще приём нужен на олимпиадах и в соревновательном программировании: слияние кучек по кругу, оптимальное дерево поиска, разрезание на большом числе точек. Если вы уже знаете оптимизацию «разделяй и властвуй», Кнут — её близкий родственник: та же идея монотонного оптимума, только окно задают два соседних отрезка, а не рекурсия.

Чтобы закрепить, решите LeetCode 1547 сначала наивно, потом с окном, и сравните оба решения стресс-тестом. Если ответы совпали на тысяче случайных входов, вы поняли главное: оптимизация Кнута — это не формула, которую вставляют вслепую, а гипотеза, которую проверяют.

Потренироваться в спокойной обстановке

Все задачи