Оптимизация ДП «разделяй и властвуй» и оптимизация Кнута: от O(kn²) к O(kn log n)
Divide and conquer DP и оптимизация Кнута простыми словами: монотонность точки оптимума, неравенство четырёхугольника, код на Python с проверкой, замеры и задачи, где это работает.
Коротко
| Приём | Вид перехода | Условие | Было | Стало |
|---|---|---|---|---|
| Разделяй и властвуй (DC) | ||||
| Кнут, слои | то же | |||
| Кнут, отрезки |
- Главная идея обоих приёмов: точка, в которой достигается минимум, монотонно сдвигается вправо. Значит, не надо перебирать все варианты — достаточно искать в окне, которое задают уже посчитанные соседи.
- Достаточное условие: функция стоимости удовлетворяет неравенству четырёхугольника при .
- Когда что брать: DC проще написать и он выгоднее при малом числе слоёв k; Кнут — при большом k и в задачах на отрезках (оптимальное дерево поиска, слияние камней).
- Главная ловушка: монотонность оптимума надо доказать или хотя бы проверить стресс-тестом. Если её нет, оба приёма молча выдают неверный ответ.
Задача, на которой всё видно
Дан массив из n неотрицательных чисел. Нужно разрезать его на ровно k непустых непрерывных групп так, чтобы сумма квадратов сумм групп была минимальной.
Например, [1, 2, 3, 4, 5] на 2 группы: [1, 2, 3] [4, 5] даёт , [1, 2, 3, 4] [5] — , [1, 2] [3, 4, 5] — . Лучший ответ — 117.
Это прототип целого класса задач «разбей последовательность на k кусков, каждый кусок чего-то стоит»: распределить задачи между k работниками, расставить k почтовых ящиков вдоль улицы, рассадить людей по k гондолам так, чтобы минимизировать суммарную неприязнь. Меняется только стоимость куска .
Наивная динамика
— минимальная стоимость разбить первые i элементов на t групп. Последняя группа — элементы с индексами , перед ней первые j элементов разбиты на групп:
где pre — префиксные суммы, чтобы стоимость куска считалась за .
INF = float('inf') def split_naive(a: list[int], k: int) -> int: n = len(a) pre = [0] for x in a: pre.append(pre[-1] + x) def cost(j: int, i: int) -> int: # отрезок a[j..i-1] return (pre[i] - pre[j]) ** 2 prev = [0] + [INF] * n # 0 групп: разбить можно только пустой префикс for _ in range(k): cur = [INF] * (n + 1) for i in range(1, n + 1): cur[i] = min(prev[j] + cost(j, i) for j in range(i)) prev = cur return prev[n]
Слоёв k, в каждом n состояний, у каждого до n переходов: . При , на Python это 4 секунды, при — уже минуты. Если вы не знакомы с базовой техникой, начните со статьи ДП для начинающих.
Наблюдение: оптимум сдвигается вправо
Обозначим через самое левое j, на котором достигается минимум для , — то есть где начинается последняя группа в оптимальном разбиении первых i элементов.
Интуиция: если добавить в конец ещё один элемент, последней группе становится «тяжелее», и выгодно начать её не раньше, чем раньше. Последняя группа может только сжаться слева, но не вырасти:
Это свойство и есть ключ. Наивный алгоритм для каждого i перебирает j от 0 до , не пользуясь тем, что уже знает про соседей. А знает он многое: если , то для всех искать раньше 120 бессмысленно, а для всех — позже 120.
Оптимизация «разделяй и властвуй»
Используем монотонность рекурсивно:
- Возьмём середину диапазона,
mid, и честно найдём перебором j в известном окне[opt_lo, opt_hi]. - Для всех i левее
midоптимум лежит в[opt_lo, opt(mid)]. - Для всех i правее
mid— в[opt(mid), opt_hi]. - Рекурсивно решаем обе половины.
def split_dc(a: list[int], k: int) -> int: n = len(a) pre = [0] for x in a: pre.append(pre[-1] + x) def cost(j: int, i: int) -> int: return (pre[i] - pre[j]) ** 2 prev = [0] + [INF] * n for _ in range(k): cur = [INF] * (n + 1) def solve(lo: int, hi: int, opt_lo: int, opt_hi: int) -> None: """Считает cur[lo..hi], зная, что оптимум лежит в [opt_lo, opt_hi].""" if lo > hi: return mid = (lo + hi) // 2 best, best_j = INF, opt_lo for j in range(opt_lo, min(mid - 1, opt_hi) + 1): value = prev[j] + cost(j, mid) if value < best: best, best_j = value, j cur[mid] = best solve(lo, mid - 1, opt_lo, best_j) solve(mid + 1, hi, best_j, opt_hi) solve(1, n, 0, n - 1) prev = cur return prev[n] print(split_dc([1, 2, 3, 4, 5], 2)) # 117
Обратите внимание на min(mid - 1, opt_hi): последняя группа не может быть пустой, поэтому . И на строгое < при сравнении: так мы берём самый левый оптимум, для него монотонность и формулируется.
Почему на слой
Глубина рекурсии — , как у сортировки слиянием: диапазон [lo, hi] каждый раз делится пополам. На одном уровне рекурсии окна [opt_lo, opt_hi] соседних вызовов пересекаются только в одной точке — правый край одного окна равен левому краю следующего. Поэтому на уровне суммарно перебирается вариантов, а на всех уровнях — . С k слоями: .
Важное отличие от наивного ДП: внутри слоя значения считаются не слева направо, а в порядке рекурсии. Это работает, потому что cur[mid] зависит только от предыдущего слоя prev, а не от соседей в текущем. Если в вашем переходе зависит от того же слоя (одномерная динамика ), DC в таком виде не применим — там смотрите в сторону Convex Hull Trick или более сложных техник.
Оптимизация Кнута для слоёв
Если монотонность есть не только внутри слоя, но и между слоями,
то окно для зажато между двумя уже известными числами. Интуиция для нижней границы: когда групп больше, последней группе можно позволить быть короче, и она не начинается раньше, чем при меньшем числе групп.
Чтобы правая граница была известна, внутри слоя идём справа налево:
def split_knuth(a: list[int], k: int) -> int: n = len(a) pre = [0] for x in a: pre.append(pre[-1] + x) def cost(j: int, i: int) -> int: return (pre[i] - pre[j]) ** 2 prev = [0] + [INF] * n prev_opt = [0] * (n + 2) # для первого слоя оптимум всегда j = 0 for _ in range(k): cur = [INF] * (n + 1) cur_opt = [0] * (n + 2) cur_opt[n + 1] = n - 1 # фиктивная правая граница for i in range(n, 0, -1): best, best_j = INF, prev_opt[i] for j in range(prev_opt[i], min(cur_opt[i + 1], i - 1) + 1): value = prev[j] + cost(j, i) if value < best: best, best_j = value, j cur[i], cur_opt[i] = best, best_j prev, prev_opt = cur, cur_opt return prev[n]
Сколько здесь работы? Длина окна для пары — это . Если сложить по всем парам, слагаемые сокращаются телескопически вдоль диагоналей таблицы , и в сумме получается — для это , независимо от k.
Замеры: кто быстрее
Все три функции проверены друг против друга на 3000 случайных тестах (n до 12), ответы совпадают. Теперь скорость на Python, массив из 2000 случайных чисел от 1 до 100:
| k | наивное ДП | разделяй и властвуй | Кнут |
|---|---|---|---|
| 20 | 4,25 с | 0,07 с | 0,23 с |
| 200 | — | 0,49 с | 0,43 с |
| 1000 | — | 2,43 с | 0,80 с |
Картина ровно такая, как предсказывает асимптотика. При малом k намного меньше , и DC выигрывает. Когда дорастает до n, Кнут обгоняет. На практике:
- k маленькое (до десятков), n большое (до ) — разделяй и властвуй. Кнут с его тут просто не влезет.
- k сравнимо с n, n до нескольких тысяч — Кнут.
- Если сомневаетесь, какой из двух писать, DC проще и требует более слабого условия — только монотонность внутри слоя.
Оптимизация Кнута для отрезков
Исторически приём появился не в задачах «разбей на k групп», а в динамике по отрезкам. В 1971 году Дональд Кнут построил алгоритм для оптимального дерева поиска за вместо , а в 1980 году Фрэнсис Яо обобщила условие до неравенства четырёхугольника.
Задача: есть n ключей в отсортированном порядке и частоты обращений к ним. Построить двоичное дерево поиска, в котором сумма «частота × глубина» минимальна. Если корень дерева на отрезке ключей — ключ r, то левое поддерево строится из , правое из , а все ключи отрезка опускаются на один уровень:
Это классическая динамика по отрезкам за . Кнут доказал, что оптимальный корень монотонен: . Добавить ключ справа — корень не сдвинется влево; убрать ключ слева — тоже.
def optimal_bst(freq: list[int]) -> int: """Минимальная сумма freq[i] * глубина(i) (корень на глубине 1).""" n = len(freq) pre = [0] for f in freq: pre.append(pre[-1] + f) # dp[i][j] — стоимость дерева из ключей i..j-1 (полуинтервал), dp[i][i] = 0 dp = [[0] * (n + 1) for _ in range(n + 1)] opt = [[0] * (n + 1) for _ in range(n + 1)] for i in range(n): dp[i][i + 1] = freq[i] opt[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 ищем только между соседними оптимумами for r in range(opt[i][j - 1], opt[i + 1][j] + 1): value = dp[i][r] + dp[r + 1][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(optimal_bst([34, 8, 50])) # 142
Проверка на примере: корень — ключ с частотой 50 (глубина 1), под ним ключ 34 (глубина 2), под ним 8 (глубина 3): . Функция сверена с переборной рекурсией на 2000 случайных наборов.
Почему : при фиксированной длине отрезка сумма длин окон по всем i телескопически сокращается до . Длин n, итого . Тот же приём для слияния камней разобран в статье про ДП по отрезкам.
Когда монотонность гарантирована
Перебирать окно вместо всего диапазона можно только если монотонность действительно есть. Стандартное достаточное условие — неравенство четырёхугольника (quadrangle inequality) для функции стоимости:
Словами: два «перекрещенных» отрезка в сумме не дороже, чем внешний плюс внутренний. Для задачи на отрезках Кнута — Яо нужно ещё одно условие — монотонность по вложению: , если .
Проверим для квадрата суммы. Пусть — суммы на кусках , , :
Неравенство выполняется, если элементы неотрицательны. С отрицательными числами может быть меньше нуля, и всё ломается — стресс-тест ниже на массивах с числами от −9 до 9 нашёл 701 нарушение монотонности из 3000 тестов. Это хороший пример того, как условие задачи «числа неотрицательны» оказывается не украшением, а частью решения.
Другие стоимости, для которых неравенство выполняется:
- сумма расстояний до медианы на отрезке отсортированных точек (почтовые ящики);
- число пар равных элементов на отрезке;
- сумма матрицы «неприязни» по квадрату с неотрицательными элементами (Ciel and Gondolas).
А вот максимум на отрезке — нет. Это легко проверить руками: a = [4, 5, 2, 7], k = 2, стоимость группы — её максимум. Для (префикс [4, 5, 2]) лучшее разбиение [4, 5] [2] с оптимумом , а для лучшее [4] [5, 2, 7] с оптимумом . Оптимум сдвинулся влево, DC вернёт 12 вместо правильных 11. Поэтому LeetCode 1335. Minimum Difficulty of a Job Schedule этой оптимизацией в лоб не решается.
Стресс-тест вместо доказательства
На контесте и на собеседовании доказывать неравенство четырёхугольника долго. Практичный путь — проверить монотонность наивным ДП на маленьких случайных тестах:
import random def opt_is_monotone(n: int, k: int, cost) -> bool: """Наивное ДП, которое запоминает самый левый оптимум и проверяет его монотонность.""" INF = float('inf') prev = [0] + [INF] * n for _ in range(k): cur, opt = [INF] * (n + 1), [0] * (n + 1) for i in range(1, n + 1): for j in range(i): value = prev[j] + cost(j, i) if value < cur[i]: cur[i], opt[i] = value, j reachable = [opt[i] for i in range(1, n + 1) if cur[i] < INF] if any(x > y for x, y in zip(reachable, reachable[1:])): return False prev = cur return True def stress(make_cost, trials: int = 2000) -> bool: for _ in range(trials): n = random.randint(1, 8) a = [random.randint(0, 9) for _ in range(n)] if not opt_is_monotone(n, random.randint(1, n), make_cost(a)): print('контрпример:', a) return False return True def square_of_sum(a): pre = [0] for x in a: pre.append(pre[-1] + x) return lambda j, i: (pre[i] - pre[j]) ** 2 def max_on_segment(a): return lambda j, i: max(a[j:i]) print(stress(square_of_sum)) # True print(stress(max_on_segment)) # печатает контрпример и False
Пара тысяч тестов на n до 8 отрабатывает за секунды. Стресс-тест не доказательство, но ловит подавляющее большинство случаев, когда оптимизация неприменима.
Пример с собеседования: почтовые ящики
LeetCode 1478. Allocate Mailboxes: дома стоят в точках прямой, нужно поставить k почтовых ящиков так, чтобы сумма расстояний от каждого дома до ближайшего ящика была минимальной.
Отсортируем дома. Каждый ящик обслуживает непрерывную группу соседних домов, а внутри группы ящик выгоднее всего ставить в медиану. Получаем ровно нашу схему «разбей на k групп» со стоимостью «сумма расстояний до медианы», которую тоже считаем через префиксные суммы за :
def min_distance(houses: list[int], k: int) -> int: h = sorted(houses) n = len(h) pre = [0] for x in h: pre.append(pre[-1] + x) def cost(j: int, i: int) -> int: """Один ящик на дома h[j..i-1]: ставим в медиану.""" m = (j + i - 1) // 2 left = h[m] * (m - j) - (pre[m] - pre[j]) right = (pre[i] - pre[m + 1]) - h[m] * (i - m - 1) return left + right INF = float('inf') prev = [0] + [INF] * n for _ in range(k): cur = [INF] * (n + 1) def solve(lo: int, hi: int, opt_lo: int, opt_hi: int) -> None: if lo > hi: return mid = (lo + hi) // 2 best, best_j = INF, opt_lo for j in range(opt_lo, min(mid - 1, opt_hi) + 1): value = prev[j] + cost(j, mid) if value < best: best, best_j = value, j cur[mid] = best solve(lo, mid - 1, opt_lo, best_j) solve(mid + 1, hi, best_j, opt_hi) solve(1, n, 0, n - 1) prev = cur return prev[n] print(min_distance([1, 4, 8, 10, 20], 3)) # 5 print(min_distance([2, 3, 5, 12, 18], 2)) # 9
В оригинальной задаче , и проходит даже с подсчётом стоимости в лоб. Но на собеседовании такой разбор хорошо показывает уровень: сначала наивное ДП, потом стоимость за через префиксные суммы, потом «а если n будет ?» — и оптимизация с объяснением, почему оптимум монотонен.
Сложность
| Вариант | Время | Память |
|---|---|---|
| Наивное «k групп» | на слой | |
| Разделяй и властвуй | на слой + стек | |
| Кнут, слои | на слой | |
| Наивное ДП по отрезкам | ||
| Кнут, отрезки |
Оценки предполагают, что считается за . Если стоимость сложнее — например, число пар равных элементов на отрезке, — в DC её можно поддерживать двумя указателями, сдвигая границы отрезка как в алгоритме Мо: суммарное число сдвигов на уровне рекурсии тоже . Так решается Codeforces 868F. Yet Another Minimization Problem.
Типичные ошибки
- Применить без проверки монотонности. Код не падает, просто выдаёт неверный ответ на части тестов. Всегда либо доказывайте неравенство четырёхугольника, либо гоняйте стресс-тест против наивного ДП.
- Не учесть знак чисел. Квадрат суммы монотонен только для неотрицательных элементов.
- Брать самый правый оптимум в одном месте и самый левый в другом. При равных значениях монотонность гарантируется для последовательного выбора: везде строгое
<(самый левый) или везде<=(самый правый). Смешение ломает окна. - Пустые группы. Граница
min(mid - 1, opt_hi)в DC иmin(cur_opt[i + 1], i - 1)у Кнута запрещают . Без неё алгоритм может «разбить» массив на k групп, часть которых пусты. - Неправильный порядок у Кнута. Для слоёв внутри слоя нужно идти справа налево, иначе ещё не посчитан. Для отрезков — по возрастанию длины, как в любой динамике по отрезкам.
- Глубина рекурсии. В DC глубина всего , так что
sys.setrecursionlimitне нужен — если вам понадобился, скорее всего, где-то ошибка в границах. - Путать с другими оптимизациями. Если переход — произведение «функция от j» × «функция от i», это Convex Hull Trick. Если ограничение на число групп k мешает, а без него задача решается быстро, — смотрите в сторону «лямбда-оптимизации» (Aliens trick, по задаче IOI 2016). А если ответ — максимум, а не сумма, как в LeetCode 410. Split Array Largest Sum, проще бинпоиск по ответу.
Где встречается
На собеседованиях в обычные компании эти оптимизации почти не спрашивают: достаточно уверенно написать наивную динамику. Но в сильных командах (алгоритмические отделы, HFT, поиск) вопрос «а можно быстрее?» после — нормальное продолжение. Хороший ответ: заметить монотонность оптимальной границы, объяснить её интуитивно («добавили элемент в конец — последняя группа не растёт влево») и описать DC с оценкой . Писать код Кнута на доске обычно не просят, но упомянуть его как альтернативу при большом k — плюс.
На олимпиадах и Codeforces это стандартный инструмент уровня Div. 1:
- Codeforces 321E. Ciel and Gondolas — каноническая задача на DC, , ;
- Codeforces 868F. Yet Another Minimization Problem — DC со стоимостью, поддерживаемой указателями;
- оптимальное дерево поиска и слияние камней — классика на Кнута;
- LeetCode 1478. Allocate Mailboxes — мягкий вход в тему.
Если динамика вам пока даётся тяжело, сначала закрепите ДП по отрезкам и задачу о рюкзаке, а к оптимизациям возвращайтесь, когда наивное решение пишется без раздумий.