Оптимизация Кнута — Яо
Оптимизация Кнута — Яо — стандартная оптимизация динамики, позволяющая решать два весьма разных типа динамики (если динамика удовлетворяет некоторому условию, о котором мы поговорим позже):
- Задача об оптимальном разбиении массива из $n$ элементов на $k$ подотрезков
$dp[ki][ni] = \min_{i < ni} dp[ki - 1][i] + w(i, ni)$ - Динамика по подотрезкам
$dp[l][r] = w(l, r) + \min_{l < i < r} dp[l][i] + dp[i][r]$
Оба варианта решаются при помощи этой оптимизации за время $O(n^2)$, при том что без оптимизации они решаются за $O(n^2 k)$ и $O(n^3)$ соответственно.
Замечание: Чаще эта оптимизация называется просто оптимизацией Кнута, однако Кнут придумал, как использовать эту оптимизацию в одном конкретном случае (для построения оптимального двоичного дерева поиска), и его доказательства были слишком сложными. Фрэнсис Яо значительно упростила доказательства Кнута и придумала очень простые условия, гарантирующие корректность этой оптимизации для большого класса других задач.
Воспринимать материал на какой-то абстрактной задаче может быть тяжело, поэтому давайте сразу сформулируем конкретные примеры задач.
Алгоритм
Задача об оптимальном разбиении массива на $k$ подотрезков
Задача: Дан массив неотрицательных чисел $a$ длины $n$. Назовем мощностью подотрезка квадрат суммы его элементов. Необходимо разбить массив $a$ на $k$ подотрезков таким образом, чтобы минимизировать сумму мощностей подотрезков разбиения. Иными словами, выделить такие $k - 1$ чисел (границы подотрезков разбиения) $i_1$, $i_2$, $\ldots$, $i_{k - 1}$, чтобы
$$(a_1 + a_2 + \ldots + a_{i_1 - 1})^2 + (a_{i_1} + a_{i_1 + 1} + \ldots + a_{i_2 - 1})^2 + \ldots + (a_{i_{k - 1}} + \ldots + a_{n})^2$$
было минимально.
В нашем случае $dp[ki][ni]$ — минимальная стоимость разбиения первых $n$ элементов на $ki$ подотрезков, а $w(i, ni)$ — мощность подотрезка $(i, ni]$, то есть $(a_{i + 1} + a_{i + 2} + \ldots + a_{ni})^2$. Далее везде мы будем подразумевать, что $w(i, ni)$ можно считать за $O(1)$. Для этого необходимо заранее посчитать префиксные суммы массива $a$ и выразить мощность подотрезка через квадрат разности префиксных сумм его концов.
Базовый алгоритм решает эту задачу за $O(n^2 k)$: мы перебираем количество отрезков по возрастанию, перебираем индекс $ni$, после чего перебираем все возможные индексы $i$ и выбираем среди них оптимальный ответ. Сходу совершенно не ясно, где здесь есть место для улучшения.
Нашу динамику можно представить как таблицу $k \times n$, и $ki$-й ее слой пересчитывается через $ki-1$-й. Тогда давайте заметим, что не обязательно перебирать индексы $ni$ по возрастанию, мы можем перебирать их в любом порядке, в котором нам захочется.
Давайте заметим, что если бы мы для каждой точки $ni$ откуда-то узнали оптимальные точки $i$, через которые нужно пересчитываться, то мы бы могли просто для каждого $ni$ обновить ответ $dp[ki][ni] := dp[ki - 1][i] + w(i, ni)$. Давайте обозначим такое оптимальное $i$ как $opt[ki][ni]$ (если есть несколько индексов $i$, дающих оптимальный ответ, выберем среди них наименьший). Тогда зная $opt[ki][ni]$, мы можем за $O(1)$ найти $dp[ki][ni]$.
Но как же нам найти $opt[ki][ni]$? В этом нам поможет то самое условие, о котором говорилось в начале статьи, которое мы должны наложить на динамику, чтобы оптимизация Кнута — Яо работала.
Условие монотонности точки разреза по обеим координатам: Оптимизация Кнута — Яо работает тогда и только тогда, когда $opt[ki - 1][ni] \le opt[ki][ni] \le opt[ki][ni + 1]$ для любых $ki$ и $ni$.
Иными словами, при фиксированном $ki$ точка пересчета $opt[ki][ni]$ должна не убывать по $ni$, то есть чем правее $ni$, тем правее левый конец последнего отрезка. А также при фиксированном $ni$ точка пересчета $opt[ki][ni]$ должна не убывать по $ki$, то есть чем больше отрезков мы можем использовать, тем короче должен быть последний отрезок. Иными словами, в матрице $opt$ возрастают и строки, и столбцы. Если подумать, то можно понять, что эти два условия весьма логичны в общем случае, так что часто они действительно выполняются.
О том, почему эти условия выполняются в нашей задаче, мы поговорим позже. Пока что мы просто примем это на веру. На самом деле чаще всего в задачах на оптимизации динамики вы не доказываете, что необходимые условия выполняются, а лишь интуитивно это понимаете или просто верите в это.
Как же эти условия помогут нам решить задачу? Да очень просто! Давайте перебирать количество подотрезков разбиения $ki$ по возрастанию, а индекс $ni$ по убыванию. Тогда в момент, когда мы хотим посчитать $opt[ki][ni]$, уже посчитаны $opt[ki - 1][ni]$ и $opt[ki][ni + 1]$, поэтому ответ нам нужно искать между ними.
Для большего понимания приведем код алгоритма:
for(int ki = 1; ki <= k; ki++) {
for(int ni = n - 1; ni >= 0; ni--) {
int from = opt[ki - 1][ni]; // opt[0][ni] = 0
int to = opt[ki][ni + 1]; // opt[ki][n] = n - 1
for(int i = from; i <= to; i++) {
if(dp[ki][ni] > dp[ki - 1][i] + w(i, ni)) {
dp[ki][ni] = dp[ki - 1][i] + w(i, ni);
opt[ki][ni] = i;
}
}
}
}
Замечание: Заметьте, что так как мы высчитываем все оптимальные точки пересчета, то мы можем при необходимости использовать их для восстановления оптимального разбиения без каких-либо проблем.
Почему же этот код будет работать за $O(n^2)$? Давайте проанализируем количество итераций, которые мы делаем. Для каждой конкретной пары $ki$, $ni$ мы делаем $opt[ki][ni + 1] - opt[ki - 1][ni] + 1$ операций (мы считаем, что $opt[0][ni] = 0$ и $opt[ki][n] = n - 1$). Интуитивно почти каждое слагаемое $opt[ki][ni]$ побывает в итоговой сумме один раз с плюсом и один раз с минусом и сократится. А если формально, то итоговое время работы — это сумма времен работы по всем парам $ki$, $ni$:
$$\sum_{ki = 1}^k \sum_{ni = 0}^{n - 1} (opt[ki][ni + 1] - opt[ki - 1][ni] + 1) = \sum_{ki = 1}^k \sum_{ni = 0}^{n - 1} opt[ki][ni + 1] - \sum_{ki = 1}^k \sum_{ni = 0}^{n - 1} opt[ki - 1][ni] + \sum_{ki = 1}^k \sum_{ni = 0}^{n - 1} 1 = $$
$$ = \sum_{ki = 1}^k \sum_{ni = 0}^{n - 1} opt[ki][ni + 1] - \sum_{ki = 1}^k \sum_{ni = 0}^{n - 1} opt[ki - 1][ni] + kn$$
Заметим, что почти все $opt[i][j]$ побывают в этой сумме один раз с плюсом и один раз с минусом. Только с плюсом побывают те элементы, для которых $ki - 1 \neq i$ ни для одного $ki$. Это значит, что $i = k$, то есть это последняя строчка матрицы. Кроме того только с плюсом войдут элементы $opt[i][n] = n - 1$, которые формально не принадлежат нашей матрице. Только с минусом аналогично войдут элементы, для которых $ni + 1 \neq j$ ни для какого $ni$. Это значит, что $j = 0$, то есть это первая строка матрицы. Кроме того только с минусом войдут элементы $opt[0][j] = 0$, которые опять же формально не принадлежат нашей матрице.
Если сократить все одинаковые слагаемые, наша асимптотика будет иметь такой вид:
$$kn + \sum_{ni = 0}^{n - 1} opt[k][ni] + \sum_{ki = 1}^k opt[i][n] - \sum_{ki = 1}^{k} opt[ki][0] - \sum_{ni = 0}^{n - 1} opt[0][ni] \le $$
$$ \le kn + n \cdot n + k \cdot n - k \cdot 0 - n \cdot 0 = n \cdot (k + n + k) = O(n^2)$$
Последнее равенство верно, потому что мы разбиваем на $k$ подотрезков, а значит, $k \le n$.
Эту асимптотику можно было понять немного иначе: посмотрим отдельно на каждую диагональ (то есть пары $ki$, $ni$ с фиксированной разностью). Можно легко заметить, что отрезки, по которым пробегается цикл для элементов этой диагонали, пересекаются только по концам, так что для каждой диагонали мы работаем за $O(n)$. Так как диагоналей всего $n + k - 1$, то итоговая асимптотика — $O(n \cdot (n + k)) = O(n^2)$.
Замечание: Если вы знакомы с оптимизацией динамики разделяй-и-властвуй, то вы могли заметить, что она решает точно такую же задачу о разбиении на $k$ подотрезков за время $O(n k \log n)$. При этом для разделяй-и-властвуй необходимо только условие монотонности точки разреза по $ni$ (только условие $opt[ki][ni] \le opt[ki][ni + 1]$).
Поэтому если в задаче применима оптимизация Кнута — Яо, то в ней применима и оптимизация разделяй-и-властвуй. Они имеют несравнимые асимптотики, и в зависимости от $k$ одна оптимизация может быть лучше другой. Если $k < \frac{n}{\log n}$, то оптимизация разделяй-и-властвуй будет быстрее, а при $k > \frac{n}{\log n}$ быстрее будет оптимизация Кнута — Яо. Однако стоит заметить, что оптимизация Кнута — Яо сильно проще в написании (просто три вложенных цикла), а также имеет меньшую константу в асимптотике в силу своей простоты (никакой рекурсии как в разделяй-и-властвуй), так что при возможности стоит использовать именно ее, пока $k$ не значительно меньше $n$.
Динамика по подотрезкам
Абсолютно аналогично эту же оптимизацию можно применить для задачи динамики по подотрезкам вида
$$dp[l][r] = w(l, r) + \min_{l < i < r} dp[l][i] + dp[i][r]$$
Сразу обратимся к примеру задачи.
Задача: Есть последовательность из $n$ кучек камней. В $i$-й из них $a_i$ камней. За одну операцию можно объединить две соседние кучки камней в одну, и если в них суммарно было $x$ камней, то эта операция стоит $x$ монет. Необходимо объединить все кучки в одну, заплатив минимальное количество монет.
Если мы обозначим стоимость объединения всех кучек с $l$-й по $r$-ю (левая граница включительно, а правая не включительно) за $dp[l][r]$, то формула пересчета динамики будет именно такой, какой нужно:
$$dp[l][r] = w(l, r) + \min_{l < i < r} dp[l][i] + dp[i][r]$$
где $w(l, r)$ — это сумма размеров кучек на полуинтервале от $l$ до $r$. Ее можно легко высчитывать при помощи префиксных сумм. Ответ, соответственно, будет храниться в $dp[0][n]$.
Упражнение: Опытному читателю, который уже знаком с другими стандартными задачами на оптимизацию Кнута — Яо, остается в качестве упражнения понять, почему эта задача, а также задачи построения оптимального двоичного дерева поиска и построения оптимального префиксного кода с сохранением порядка, — это на самом деле одни и те же задачи.
Обозначим оптимальное $i$ в пересчете динамики за $opt[l][r]$. Тогда утверждается, что опять же выполняется условие монотонности точки разреза по обеим координатам, как и в предыдущей задаче. Значит, мы можем применить оптимизацию Кнута — Яо, перебирая левую границу отрезка по убыванию, а правую — по возрастанию (чтобы то, через что мы пересчитываемся, уже было посчитано).
for(int l = n - 1; l >= 0; l--) {
for(int r = l + 2; r <= n; r++) {
int from = opt[l][r - 1]; // opt[i][i + 1] = i
int to = opt[l + 1][r];
for(int i = from; i <= to; i++) {
if(dp[l][r] > w(l, r) + dp[l][i] + dp[i][r]) {
dp[l][r] = w(l, r) + dp[l][i] + dp[i][r];
opt[l][r] = i;
}
}
}
}
Так как этот код абсолютно аналогичен коду из предыдущей задачи (параметр $l$ аналогичен параметру $ni$, а параметр $r$ — параметру $ki$), то по тем же причинам он работает за $O(n^2)$.
Замечание: Иногда динамика по подотрезкам может отличаться в своей формулировке. Формула может выглядеть так:
$$dp[l][r] = \min_{l < i < r} dp[l][i] + dp[i][r] + w(l, i) + w(i, r)$$
Однако легко заметить, что эта динамика отличается лишь тем, что мы прибавляем стоимость подотрезка немного позже. Итоговое значение такой динамики изменится просто на $w(0, n) - \sum_i w(i, i + 1)$, а оптимальное разбиение останется тем же самым.
Достаточное условие для монотонности точки разреза
Как мы уже поняли, необходимыми и достаточными условиями для работы оптимизации Кнута — Яо являются условия монотонности точки разреза по обеим координатам, то есть $opt[ki - 1][ni] \le opt[ki][ni] \le opt[ki][ni + 1]$ для любых $ki$ и $ni$. Однако практика показывает, что доказать это утверждение обычно сложно, если не знать, как к нему подступиться. В этом разделе мы познакомимся с достаточным условием на то, чтобы условие монотонности точки разреза выполнялось, которое чаще всего несложно проверить.
Достаточные условия будут немного отличаться для двух разных видов задач, которые мы рассмотрели ранее, поэтому мы посмотрим на них отдельно.
Достаточное условие для задачи оптимального разбиения на $k$ подотрезков
Если наша задача имеет первый вид, то есть
$$dp[ki][ni] = \min_{i < ni} dp[ki - 1][i] + w(i, ni)$$
То необходимым условием для выполнения условия монотонности точки разреза по обеим координатам является неравенство четырехугольника для функции $w$. Определения и доказательства можно прочитать в специальной статье про неравенство четырехугольника.
Достаточное условие для задачи динамики по подотрезкам
Если наша задача имеет второй вид, то есть
$$dp[l][r] = w(l, r) + \min_{l < i < r} dp[l][i] + dp[i][r]$$
То для монотонности точки разреза по обеим координатам необходимы уже два условия: неравенство четырехугольника для $w$, а также монотонность функции $w$. Определения и доказательства опять же можно прочитать в специальной статье про неравенство четырехугольника.
Оптимизация Кнута — Яо для трудновычислимых стоимостей подотрезков разбиения
Везде ранее мы подразумевали, что $w(l, r)$ можно вычислить за $O(1)$ для любых индексов $l$ и $r$. Однако это не всегда верно. Бывают ситуации, в которых функция $w$ устроена каким-то сложным образом. В этом случае на помощь может прийти один простой трюк. Даже если функцию $w$ вычислить сложно, бывает нетрудно пересчитать функцию $w$, если подвинуть одну из границ на единицу влево или вправо. Если это возможно, то вычисление каждого нового значения $w$ можно выразить через последовательное движение границ предыдущего посчитанного отрезка к новому. Несложно доказать, что таких движений произойдет суммарно $O(n^2)$, поэтому если передвижение любой границы на единицу в любую сторону можно выполнять за $O(1)$, то асимптотика решения не поменяется.
Подробнее про эту технику можно прочитать в аналогичном разделе в статье про оптимизацию разделяй-и-властвуй.