Оптимизация Кнута: интервальное ДП за O(n²) вместо O(n³)
Оптимизация Кнута для ДП по отрезкам: условие opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j], почему выходит O(n²), слияние кучек, разрезание палки и оптимальное дерево поиска на Python.
Коротко
| Что | Суть |
|---|---|
| Вид перехода | , не зависит от |
| Ключевое условие | |
| Когда оно верно | удовлетворяет неравенству четырёхугольника и монотонна по вложению отрезков |
| Было → стало | по времени, память |
| Классические задачи | слияние кучек (линейное и по кругу), разрезание палки, оптимальное дерево поиска |
- Идея в одну строку: перебирать точку разреза не на всём отрезке, а только между оптимумами двух соседних, уже посчитанных отрезков.
- Почему : для каждой длины отрезка длины окон телескопически складываются в .
- Главная ловушка: если стоимость зависит от точки разреза (цепочка матриц, Burst Balloons), приём молча даёт неверный ответ.
Сама динамика по отрезкам — порядок обхода, состояние , разбор цепочки матриц и Burst Balloons — есть в статье про ДП по отрезкам. Родственный приём для задач «разбей массив на k групп» и общая теория монотонности оптимума — в статье про оптимизацию «разделяй и властвуй». Здесь — только Кнут на отрезках, но подробно: откуда берётся окно, как не ошибиться с границами и где приём применять нельзя.
Шаблон, который распознаёт оптимизация
Оптимизация Кнута работает с переходом строго определённой формы. Удобнее всего писать его на полуинтервалах :
Отрезок режется точкой на две части, решения частей складываются, и сверху добавляется стоимость , которая зависит только от концов отрезка. Обозначим — точку , на которой достигается минимум.
Наивное решение перебирает по всему отрезку: состояний по вариантов, итого . При на Python это около 10 миллионов итераций внутреннего цикла и 2 секунды — уже на грани лимитов. При наивный вариант безнадёжен даже на C++.
Оптимизация Кнута говорит: если выполнено
то достаточно перебирать только в этом окне. Оба края окна уже посчитаны: отрезки и на единицу короче, а мы идём по возрастанию длины.
Интуиция у условия простая. Добавили элемент справа — точка разреза не уедет влево. Убрали элемент слева — тоже не уедет влево. Оптимальный разрез «следует» за отрезком.
Почему окно правильное
Достаточное условие — функция удовлетворяет двум свойствам при :
- Неравенство четырёхугольника: .
- Монотонность по вложению: — объемлющий отрезок не дешевле вложенного.
Сумма на отрезке неотрицательных чисел удовлетворяет обоим: в первом неравенстве обе части равны, а второе следует из неотрицательности. Именно такая стоимость стоит в слиянии кучек, разрезании палки и задаче об оптимальном дереве.
Дальше доказательство идёт в два шага. Первый шаг — лемма Яо: если обладает обоими свойствами, то и сама удовлетворяет неравенству четырёхугольника. Доказывается индукцией по длине отрезка, и это самая техническая часть — её можно принять на веру.
Второй шаг короткий, и его полезно понимать, потому что он объясняет, откуда берётся окно. Обозначим — значение, которое даёт разрез для отрезка . Возьмём два разреза и применим неравенство четырёхугольника для к точкам :
Прибавим к обеим частям и перегруппируем:
Смысл: если правый разрез был не хуже левого на отрезке , то на отрезке он тоже не хуже. Значит, всё, что левее , проигрывало ему раньше и проигрывает теперь — искать там бессмысленно. Это левая граница окна. Правая доказывается зеркально.
На практике доказательство пишут редко. Гораздо чаще проверяют гипотезу стресс-тестом: наивное ДП против оптимизированного на тысячах случайных маленьких входов. Ровно так проверен весь код ниже.
Почему получается O(n²)
Зафиксируем длину отрезка . Для отрезка окно имеет длину . Сложим по всем :
Сумма телескопическая: правый край окна для — это левый край для , и почти всё сокращается. Каждая отдельная клетка может перебрать много вариантов, но в сумме по одной длине — не больше . Длин , итого .
Замеры на слиянии кучек со случайными весами подтверждают оценку:
| n | итераций, наивно | итераций, Кнут | время, наивно | время, Кнут |
|---|---|---|---|---|
| 100 | 166 650 | 9 742 | 0.024 с | 0.002 с |
| 200 | 1 333 300 | 40 256 | 0.19 с | 0.016 с |
| 400 | 10 666 600 | 158 345 | 2.0 с | 0.035 с |
При итераций почти ровно , а при оптимизированная версия на Python укладывается примерно в полсекунды. Наивная там работала бы десятки секунд.
Слияние кучек
Классическая задача: в ряд лежат кучек камней. За ход можно слить две соседние кучки, стоимость хода — суммарное число камней в них. Нужно слить всё в одну кучку с минимальной стоимостью.
Последнее слияние объединяет кучки и , и неважно, где именно , его стоимость — сумма всего отрезка. Поэтому через префиксные суммы, и переход ровно того вида, что нужен.
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). Всё остальное — обычная динамика по отрезкам.
Тонкое место — инициализация для отрезков длины 1. Разреза у них нет, но значение нужно как граница окна для длины 2. Мы кладём opt[i][i + 1] = i + 1: тогда для отрезка левая граница — единственный допустимый разрез. Правая граница opt[i + 1][i + 2] равна , это уже за пределами отрезка, поэтому min(..., j - 1). Для длин от 3 и больше обрезка не срабатывает, но и не мешает.
Функция сверена с переборной рекурсией на 2000 случайных массивов длиной до 9.
Кучки по кругу
Если кучки лежат по кругу, первая и последняя тоже соседние. Стандартный приём — удвоить массив: b = a + a, посчитать динамику на отрезках длиной до и взять минимум по всем . Каждый такой отрезок — один из способов «разрезать» круг. Оптимизация Кнута переносится без изменений: удвоенный массив по-прежнему состоит из неотрицательных чисел.
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] выгодно сначала слить две единицы через «шов» круга: , потом , потом , итого . В линию единицы не соседи, и лучшее, что получится, — .
Разрезание палки (LeetCode 1547)
В задаче Minimum Cost to Cut a Stick палку длины надо разрезать в заданных точках, а стоимость каждого разреза равна длине куска, который режем в этот момент. В статье про ДП по отрезкам она решается за , где — число разрезов.
Добавим концы палки к точкам: . Первый разрез на куске между точками и стоит — независимо от того, где режем. Это снова стоимость «длина отрезка», она линейна и монотонна, условия Кнута выполнены:
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, и кубическое решение проходит. Но если на собеседовании спросят «а если разрезов ?», это и есть правильный ответ: через оптимизацию Кнута. Заметьте, что код почти дословно повторяет слияние кучек — это одна и та же задача, прочитанная в обратном направлении.
Оптимальное дерево поиска
Именно на этой задаче Дональд Кнут в 1971 году и придумал приём. Есть ключей в отсортированном порядке. Ключ ищут раз, а между ключами и ищут отсутствующие значения раз (промахи; — левее всех ключей, — правее). Нужно построить двоичное дерево поиска, в котором суммарная стоимость поиска минимальна: успешный поиск ключа на глубине стоит сравнений, промах в «пустом месте» под ключами стоит .
Если корень отрезка ключей — ключ , то слева дерево на , справа на , и все ключи и промахи отрезка опускаются на один уровень. Это добавляет их суммарный вес :
Форма чуть другая — корень выпадает из обеих частей, — но окно то же: . Это и есть исходная теорема Кнута.
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 — это , оба варианта законные.
Проверим ответ руками. Корень — ключ 2 (вес 6) на глубине 1, под ним ключи 0 и 3 на глубине 2, ключ 1 — на глубине 3. Успешные поиски: . Промахи: под двумя ключами, под тремя, под двумя — . Итого . Сверка с переборной рекурсией и пересчётом стоимости по восстановленному дереву — 2000 случайных тестов, все совпали.
Массив root — побочный продукт оптимизации, и его же используют для восстановления ответа. Отдельная таблица для восстановления не нужна.
Где приём не работает
Самая частая ошибка — применить окно к задаче, которая лишь похожа на шаблон.
Стоимость зависит от точки разреза. В перемножении цепочки матриц переход : слагаемое зависит от , и шаблон уже не тот. Пример: размерности [1, 9, 4, 8, 8] (матрицы , , , ). Наивная динамика даёт , и для полного отрезка оптимальный разрез . При этом — правая граница окна меньше настоящего оптимума. Окно Кнута не видит правильный разрез и возвращает . Burst Balloons ломается так же: там в стоимость входит значение шарика .
Стоимость не монотонна по вложению. Если в слиянии кучек разрешить отрицательные числа, неравенство четырёхугольника для суммы всё ещё выполняется (там равенство), а монотонность — нет. Стресс-тест на числах от −9 до 9 дал 933 расхождения на 3000 тестов. Минимальный пример: [-5, -5, 8, -7], верный ответ , с окном получается .
Слияние по кучек. В LeetCode 1000. Minimum Cost to Merge Stones сливают сразу соседних кучек, и состояние приходится расширять числом кучек на отрезке. Прямолинейно приложить окно Кнута к такой динамике нельзя — сначала нужна своя проверка монотонности.
Правило простое: перед тем как сужать перебор, проверьте, что не зависит от , неотрицательна по смыслу и растёт при расширении отрезка. Если сомневаетесь — напишите наивную версию и прогоните сравнение на случайных маленьких тестах. Это пять минут, а ошибка без проверки не проявится на примерах из условия.
Детали реализации
- Порядок обхода. Нужно, чтобы и были посчитаны раньше . Обход по возрастанию длины это гарантирует. Подходит и обход « от вниз, от вверх» — оба соседа к моменту расчёта готовы.
- Хранить нужно
opt. Без таблицы оптимумов окно взять неоткуда. Память остаётся , как и у самой динамики. - Равные значения. Брать первый минимум (
<) или последний (<=) — неважно, если делать это последовательно. Стресс-тест на массивах с числами 0–3, где ничьих очень много, совпал с наивной версией в обоих вариантах. - Пустое окно. Если из-за ошибки в границах
lo > hi, цикл не выполнится,bestостанется бесконечностью, и ответ «испортится» молча. Полезно на время отладки вставитьassert best_r != -1. - Полуинтервалы или отрезки. Для слияния кучек удобнее полуинтервалы с разрезом , общим для обеих частей. Для дерева поиска — корень, который не входит ни в одну часть. Смешивать конвенции в одном коде — верный способ получить off-by-one в окне.
Сложность
| Вариант | Время | Память |
|---|---|---|
| Наивное ДП по отрезкам | ||
| С оптимизацией Кнута |
Для слияния кучек в линию существуют и более быстрые алгоритмы — Ху–Таккера и Гарсиа–Уокса, за . Они заметно сложнее и на собеседованиях не встречаются, а олимпиадные ограничения обычно рассчитаны как раз на .
Типичные ошибки
- Окно без проверки условий. Цепочка матриц, Burst Balloons, кучки с отрицательными весами — примеры, где приём даёт неверный ответ без единой ошибки выполнения.
- Забыли инициализировать
optдля коротких отрезков. Нули вopt[i][i + 1]дают окно, начинающееся левее отрезка, и разрез . - Нет обрезки правой границы. В конвенции полуинтервалов
opt[i + 1][i + 2] = i + 2выходит за отрезок — безmin(..., j - 1)получится разрез по краю. - Посчитали
opt, но не сохранили. Если записывать толькоdp[i][j], следующие отрезки берут окно из нулей. - Путаница с . Отдельная клетка может перебрать вариантов — оценка амортизированная, по всем клеткам одной длины. Пытаться доказать «окно всегда маленькое» бесполезно.
Где встречается на собеседованиях
На обычном интервью оптимизацию Кнута не требуют, но она хорошо работает как follow-up к задачам на ДП по отрезкам. Типичный сценарий: вы решили Minimum Cost to Cut a Stick или задачу о слиянии камней за , и интервьюер спрашивает, что делать при . Ответ «оптимальная точка разреза монотонна, поэтому перебираем только между и , итого » плюс пара слов о том, почему стоимость здесь подходит, — сильный сигнал.
Чаще приём нужен на олимпиадах и в соревновательном программировании: слияние кучек по кругу, оптимальное дерево поиска, разрезание на большом числе точек. Если вы уже знаете оптимизацию «разделяй и властвуй», Кнут — её близкий родственник: та же идея монотонного оптимума, только окно задают два соседних отрезка, а не рекурсия.
Чтобы закрепить, решите LeetCode 1547 сначала наивно, потом с окном, и сравните оба решения стресс-тестом. Если ответы совпали на тысяче случайных входов, вы поняли главное: оптимизация Кнута — это не формула, которую вставляют вслепую, а гипотеза, которую проверяют.