Оптимизация ДП «разделяй и властвуй» и оптимизация Кнута: от O(kn²) к O(kn log n)

Divide and conquer DP и оптимизация Кнута простыми словами: монотонность точки оптимума, неравенство четырёхугольника, код на Python с проверкой, замеры и задачи, где это работает.

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

Коротко

ПриёмВид переходаУсловиеБылоСтало
Разделяй и властвуй (DC)dpt[i]=min⁡j<i(dpt−1[j]+C(j,i))dp_t[i] = \min_{j<i}(dp_{t-1}[j] + C(j, i))optt(i)≤optt(i+1)opt_t(i) \le opt_t(i+1)O(kn2)O(kn^2)O(knlog⁡n)O(kn \log n)
Кнут, слоито жеoptt−1(i)≤optt(i)≤optt(i+1)opt_{t-1}(i) \le opt_t(i) \le opt_t(i+1)O(kn2)O(kn^2)O(n2)O(n^2)
Кнут, отрезкиdp[i][j]=min⁡i≤r<j(dp[i][r]+dp[r+1][j])+w(i,j)dp[i][j] = \min_{i \le r < j}(dp[i][r] + dp[r+1][j]) + w(i, j)opt[i][j−1]≤opt[i][j]≤opt[i+1][j]opt[i][j-1] \le opt[i][j] \le opt[i+1][j]O(n3)O(n^3)O(n2)O(n^2)
  • Главная идея обоих приёмов: точка, в которой достигается минимум, монотонно сдвигается вправо. Значит, не надо перебирать все варианты — достаточно искать в окне, которое задают уже посчитанные соседи.
  • Достаточное условие: функция стоимости удовлетворяет неравенству четырёхугольника C(a,c)+C(b,d)≤C(a,d)+C(b,c)C(a, c) + C(b, d) \le C(a, d) + C(b, c) при a≤b≤c≤da \le b \le c \le d.
  • Когда что брать: DC проще написать и он выгоднее при малом числе слоёв k; Кнут — при большом k и в задачах на отрезках (оптимальное дерево поиска, слияние камней).
  • Главная ловушка: монотонность оптимума надо доказать или хотя бы проверить стресс-тестом. Если её нет, оба приёма молча выдают неверный ответ.

Задача, на которой всё видно

Дан массив из n неотрицательных чисел. Нужно разрезать его на ровно k непустых непрерывных групп так, чтобы сумма квадратов сумм групп была минимальной.

Например, [1, 2, 3, 4, 5] на 2 группы: [1, 2, 3] [4, 5] даёт 62+92=1176^2 + 9^2 = 117, [1, 2, 3, 4] [5] — 100+25=125100 + 25 = 125, [1, 2] [3, 4, 5] — 9+144=1539 + 144 = 153. Лучший ответ — 117.

Это прототип целого класса задач «разбей последовательность на k кусков, каждый кусок чего-то стоит»: распределить задачи между k работниками, расставить k почтовых ящиков вдоль улицы, рассадить людей по k гондолам так, чтобы минимизировать суммарную неприязнь. Меняется только стоимость куска C(j,i)C(j, i).

Наивная динамика

dpt[i]dp_t[i] — минимальная стоимость разбить первые i элементов на t групп. Последняя группа — элементы с индексами j..i−1j..i-1, перед ней первые j элементов разбиты на t−1t-1 групп:

dpt[i]=min⁡0≤j<i(dpt−1[j]+C(j,i)),C(j,i)=(pre[i]−pre[j])2dp_t[i] = \min_{0 \le j < i} \big( dp_{t-1}[j] + C(j, i) \big), \qquad C(j, i) = (\text{pre}[i] - \text{pre}[j])^2

где pre — префиксные суммы, чтобы стоимость куска считалась за O(1)O(1).

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 переходов: O(kn2)O(kn^2). При n=2000n = 2000, k=20k = 20 на Python это 4 секунды, при n=104n = 10^4 — уже минуты. Если вы не знакомы с базовой техникой, начните со статьи ДП для начинающих.

Наблюдение: оптимум сдвигается вправо

Обозначим через optt(i)opt_t(i) самое левое j, на котором достигается минимум для dpt[i]dp_t[i], — то есть где начинается последняя группа в оптимальном разбиении первых i элементов.

Интуиция: если добавить в конец ещё один элемент, последней группе становится «тяжелее», и выгодно начать её не раньше, чем раньше. Последняя группа может только сжаться слева, но не вырасти:

optt(1)≤optt(2)≤⋯≤optt(n)opt_t(1) \le opt_t(2) \le \dots \le opt_t(n)

Это свойство и есть ключ. Наивный алгоритм для каждого i перебирает j от 0 до i−1i-1, не пользуясь тем, что уже знает про соседей. А знает он многое: если optt(500)=120opt_t(500) = 120, то для всех i>500i > 500 искать раньше 120 бессмысленно, а для всех i<500i < 500 — позже 120.

Оптимизация «разделяй и властвуй»

Используем монотонность рекурсивно:

  1. Возьмём середину диапазона, mid, и честно найдём opt(mid)opt(mid) перебором j в известном окне [opt_lo, opt_hi].
  2. Для всех i левее mid оптимум лежит в [opt_lo, opt(mid)].
  3. Для всех i правее mid — в [opt(mid), opt_hi].
  4. Рекурсивно решаем обе половины.
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): последняя группа не может быть пустой, поэтому j<ij < i. И на строгое < при сравнении: так мы берём самый левый оптимум, для него монотонность и формулируется.

Почему O(nlog⁡n)O(n \log n) на слой

Глубина рекурсии — log⁡2n\log_2 n, как у сортировки слиянием: диапазон [lo, hi] каждый раз делится пополам. На одном уровне рекурсии окна [opt_lo, opt_hi] соседних вызовов пересекаются только в одной точке — правый край одного окна равен левому краю следующего. Поэтому на уровне суммарно перебирается O(n)O(n) вариантов, а на всех уровнях — O(nlog⁡n)O(n \log n). С k слоями: O(knlog⁡n)O(kn \log n).

Важное отличие от наивного ДП: внутри слоя значения считаются не слева направо, а в порядке рекурсии. Это работает, потому что cur[mid] зависит только от предыдущего слоя prev, а не от соседей в текущем. Если в вашем переходе dp[i]dp[i] зависит от dp[j]dp[j] того же слоя (одномерная динамика dp[i]=min⁡j(dp[j]+C(j,i))dp[i] = \min_j(dp[j] + C(j, i))), DC в таком виде не применим — там смотрите в сторону Convex Hull Trick или более сложных техник.

Оптимизация Кнута для слоёв

Если монотонность есть не только внутри слоя, но и между слоями,

optt−1(i)≤optt(i)≤optt(i+1),opt_{t-1}(i) \le opt_t(i) \le opt_t(i+1),

то окно для optt(i)opt_t(i) зажато между двумя уже известными числами. Интуиция для нижней границы: когда групп больше, последней группе можно позволить быть короче, и она не начинается раньше, чем при меньшем числе групп.

Чтобы правая граница optt(i+1)opt_t(i+1) была известна, внутри слоя идём справа налево:

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]

Сколько здесь работы? Длина окна для пары (t,i)(t, i) — это optt(i+1)−optt−1(i)+1opt_t(i+1) - opt_{t-1}(i) + 1. Если сложить по всем парам, слагаемые сокращаются телескопически вдоль диагоналей таблицы (t,i)(t, i), и в сумме получается O(n(n+k))O(n(n + k)) — для k≤nk \le n это O(n2)O(n^2), независимо от k.

Замеры: кто быстрее

Все три функции проверены друг против друга на 3000 случайных тестах (n до 12), ответы совпадают. Теперь скорость на Python, массив из 2000 случайных чисел от 1 до 100:

kнаивное ДПразделяй и властвуйКнут
204,25 с0,07 с0,23 с
200—0,49 с0,43 с
1000—2,43 с0,80 с

Картина ровно такая, как предсказывает асимптотика. При малом k knlog⁡nkn \log n намного меньше n2n^2, и DC выигрывает. Когда klog⁡nk \log n дорастает до n, Кнут обгоняет. На практике:

  • k маленькое (до десятков), n большое (до 10510^5) — разделяй и властвуй. Кнут с его O(n2)O(n^2) тут просто не влезет.
  • k сравнимо с n, n до нескольких тысяч — Кнут.
  • Если сомневаетесь, какой из двух писать, DC проще и требует более слабого условия — только монотонность внутри слоя.

Оптимизация Кнута для отрезков

Исторически приём появился не в задачах «разбей на k групп», а в динамике по отрезкам. В 1971 году Дональд Кнут построил алгоритм для оптимального дерева поиска за O(n2)O(n^2) вместо O(n3)O(n^3), а в 1980 году Фрэнсис Яо обобщила условие до неравенства четырёхугольника.

Задача: есть n ключей в отсортированном порядке и частоты обращений к ним. Построить двоичное дерево поиска, в котором сумма «частота × глубина» минимальна. Если корень дерева на отрезке ключей [i,j)[i, j) — ключ r, то левое поддерево строится из [i,r)[i, r), правое из [r+1,j)[r+1, j), а все ключи отрезка опускаются на один уровень:

dp[i][j]=min⁡i≤r<j(dp[i][r]+dp[r+1][j])+∑t=ij−1freq[t]dp[i][j] = \min_{i \le r < j} \big( dp[i][r] + dp[r+1][j] \big) + \sum_{t=i}^{j-1} \text{freq}[t]

Это классическая динамика по отрезкам за O(n3)O(n^3). Кнут доказал, что оптимальный корень монотонен: opt[i][j−1]≤opt[i][j]≤opt[i+1][j]opt[i][j-1] \le opt[i][j] \le opt[i+1][j]. Добавить ключ справа — корень не сдвинется влево; убрать ключ слева — тоже.

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): 50+68+24=14250 + 68 + 24 = 142. Функция сверена с переборной рекурсией на 2000 случайных наборов.

Почему O(n2)O(n^2): при фиксированной длине отрезка сумма длин окон opt[i+1][j]−opt[i][j−1]+1opt[i+1][j] - opt[i][j-1] + 1 по всем i телескопически сокращается до O(n)O(n). Длин n, итого O(n2)O(n^2). Тот же приём для слияния камней разобран в статье про ДП по отрезкам.

Когда монотонность гарантирована

Перебирать окно вместо всего диапазона можно только если монотонность действительно есть. Стандартное достаточное условие — неравенство четырёхугольника (quadrangle inequality) для функции стоимости:

C(a,c)+C(b,d)≤C(a,d)+C(b,c),a≤b≤c≤dC(a, c) + C(b, d) \le C(a, d) + C(b, c), \qquad a \le b \le c \le d

Словами: два «перекрещенных» отрезка в сумме не дороже, чем внешний плюс внутренний. Для задачи на отрезках Кнута — Яо нужно ещё одно условие — монотонность по вложению: w(b,c)≤w(a,d)w(b, c) \le w(a, d), если [b,c]⊆[a,d][b, c] \subseteq [a, d].

Проверим для квадрата суммы. Пусть x,y,zx, y, z — суммы на кусках [a,b)[a, b), [b,c)[b, c), [c,d)[c, d):

[(x+y+z)2+y2]−[(x+y)2+(y+z)2]=2xz≥0\big[(x+y+z)^2 + y^2\big] - \big[(x+y)^2 + (y+z)^2\big] = 2xz \ge 0

Неравенство выполняется, если элементы неотрицательны. С отрицательными числами xzxz может быть меньше нуля, и всё ломается — стресс-тест ниже на массивах с числами от −9 до 9 нашёл 701 нарушение монотонности из 3000 тестов. Это хороший пример того, как условие задачи «числа неотрицательны» оказывается не украшением, а частью решения.

Другие стоимости, для которых неравенство выполняется:

  • сумма расстояний до медианы на отрезке отсортированных точек (почтовые ящики);
  • число пар равных элементов на отрезке;
  • C(j,i)=C(j, i) = сумма матрицы «неприязни» по квадрату [j,i)×[j,i)[j, i) \times [j, i) с неотрицательными элементами (Ciel and Gondolas).

А вот максимум на отрезке — нет. Это легко проверить руками: a = [4, 5, 2, 7], k = 2, стоимость группы — её максимум. Для i=3i = 3 (префикс [4, 5, 2]) лучшее разбиение [4, 5] [2] с оптимумом j=2j = 2, а для i=4i = 4 лучшее [4] [5, 2, 7] с оптимумом j=1j = 1. Оптимум сдвинулся влево, 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 групп» со стоимостью «сумма расстояний до медианы», которую тоже считаем через префиксные суммы за O(1)O(1):

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≤100n \le 100, и проходит даже O(kn3)O(kn^3) с подсчётом стоимости в лоб. Но на собеседовании такой разбор хорошо показывает уровень: сначала наивное ДП, потом стоимость за O(1)O(1) через префиксные суммы, потом «а если n будет 10510^5?» — и оптимизация с объяснением, почему оптимум монотонен.

Сложность

ВариантВремяПамять
Наивное «k групп»O(kn2)O(kn^2)O(n)O(n) на слой
Разделяй и властвуйO(knlog⁡n)O(kn \log n)O(n)O(n) на слой + O(log⁡n)O(\log n) стек
Кнут, слоиO(n2)O(n^2)O(n)O(n) на слой
Наивное ДП по отрезкамO(n3)O(n^3)O(n2)O(n^2)
Кнут, отрезкиO(n2)O(n^2)O(n2)O(n^2)

Оценки предполагают, что C(j,i)C(j, i) считается за O(1)O(1). Если стоимость сложнее — например, число пар равных элементов на отрезке, — в DC её можно поддерживать двумя указателями, сдвигая границы отрезка как в алгоритме Мо: суммарное число сдвигов на уровне рекурсии тоже O(n)O(n). Так решается Codeforces 868F. Yet Another Minimization Problem.

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

  1. Применить без проверки монотонности. Код не падает, просто выдаёт неверный ответ на части тестов. Всегда либо доказывайте неравенство четырёхугольника, либо гоняйте стресс-тест против наивного ДП.
  2. Не учесть знак чисел. Квадрат суммы монотонен только для неотрицательных элементов.
  3. Брать самый правый оптимум в одном месте и самый левый в другом. При равных значениях монотонность гарантируется для последовательного выбора: везде строгое < (самый левый) или везде <= (самый правый). Смешение ломает окна.
  4. Пустые группы. Граница min(mid - 1, opt_hi) в DC и min(cur_opt[i + 1], i - 1) у Кнута запрещают j=ij = i. Без неё алгоритм может «разбить» массив на k групп, часть которых пусты.
  5. Неправильный порядок у Кнута. Для слоёв внутри слоя нужно идти справа налево, иначе optt(i+1)opt_t(i+1) ещё не посчитан. Для отрезков — по возрастанию длины, как в любой динамике по отрезкам.
  6. Глубина рекурсии. В DC глубина всего log⁡2n\log_2 n, так что sys.setrecursionlimit не нужен — если вам понадобился, скорее всего, где-то ошибка в границах.
  7. Путать с другими оптимизациями. Если переход — произведение «функция от j» × «функция от i», это Convex Hull Trick. Если ограничение на число групп k мешает, а без него задача решается быстро, — смотрите в сторону «лямбда-оптимизации» (Aliens trick, по задаче IOI 2016). А если ответ — максимум, а не сумма, как в LeetCode 410. Split Array Largest Sum, проще бинпоиск по ответу.

Где встречается

На собеседованиях в обычные компании эти оптимизации почти не спрашивают: достаточно уверенно написать наивную динамику. Но в сильных командах (алгоритмические отделы, HFT, поиск) вопрос «а можно быстрее?» после O(kn2)O(kn^2) — нормальное продолжение. Хороший ответ: заметить монотонность оптимальной границы, объяснить её интуитивно («добавили элемент в конец — последняя группа не растёт влево») и описать DC с оценкой O(knlog⁡n)O(kn \log n). Писать код Кнута на доске обычно не просят, но упомянуть его как альтернативу при большом k — плюс.

На олимпиадах и Codeforces это стандартный инструмент уровня Div. 1:

  • Codeforces 321E. Ciel and Gondolas — каноническая задача на DC, n≤4000n \le 4000, k≤800k \le 800;
  • Codeforces 868F. Yet Another Minimization Problem — DC со стоимостью, поддерживаемой указателями;
  • оптимальное дерево поиска и слияние камней — классика на Кнута;
  • LeetCode 1478. Allocate Mailboxes — мягкий вход в тему.

Если динамика вам пока даётся тяжело, сначала закрепите ДП по отрезкам и задачу о рюкзаке, а к оптимизациям возвращайтесь, когда наивное решение пишется без раздумий.

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

Все задачи