Оптимизация ДПDP Optimization

Convex Hull Trick (CHT) применяется, когда переход имеет вид dp[i] = min по j<i от (dp[j] + b[j]·x[i] + c[j]) — то есть минимизация по НАБОРУ ЛИНЕЙНЫХ функций от точки запроса x[i], где для каждого j линия задаётся наклоном b[j] и сдвигом (dp[j]+c[j]). Идея: если хранить только те линии, которые хотя бы при каком-то x дают минимум (это и есть "нижняя огибающая" — нижняя часть выпуклой оболочки набора линий, отсюда название), то при добавлении новой линии можно за O(1) амортизированно определить, какие из уже сохранённых линий стали заведомо ненужными (полностью "накрыты" сверху новой и соседними), и удалить их — классическая структура данных на стеке/деке, по духу похожая на построение выпуклой оболочки (2.4.1.5). Запрос минимума в точке x[i] выполняется за O(log n) (бинарным поиском по наклонам огибающей) или амортизированно за O(1), если запросы идут в отсортированном по x порядке (двухуказательная техника вместо бинарного поиска). Итог: вместо O(n) на переход для каждого i — O(log n) или O(1), и вся ДП становится O(n log n) или O(n) вместо O(n²).The Convex Hull Trick (CHT) applies when the transition has the form dp[i] = min over j<i of (dp[j] + b[j]·x[i] + c[j]) — that is, minimizing over a SET OF LINEAR functions of the query point x[i], where for each j the line has slope b[j] and intercept (dp[j]+c[j]). The idea: if only the lines that achieve the minimum for at least some x are kept (this is the "lower envelope" — the lower part of the convex hull of the line set, hence the name), then adding a new line lets you determine in amortized O(1) which already-stored lines have become provably useless (fully "covered" from above by the new line and its neighbors) and remove them — a classic stack/deque-based data structure, similar in spirit to building a convex hull (2.4.1.5). Querying the minimum at point x[i] takes O(log n) (binary search over the envelope's slopes) or amortized O(1) if queries arrive sorted by x (a two-pointer technique instead of binary search). The result: instead of O(n) per transition for each i, it's O(log n) or O(1), and the whole DP becomes O(n log n) or O(n) instead of O(n²).

Конкретный пример, где такая форма перехода возникает естественно: разбиение массива на сегменты с минимизацией суммарной стоимости, где стоимость сегмента [j+1, i] линейна по правой границе i при фиксированной левой границе j — например, dp[i] = min по j от (dp[j] + (prefix[i]-prefix[j])²), раскрывая квадрат: dp[j] + prefix[i]² - 2·prefix[j]·prefix[i] + prefix[j]² — это линейная функция от x=prefix[i] с наклоном -2·prefix[j] и сдвигом dp[j]+prefix[j]² (слагаемое prefix[i]² общее для всех j и не участвует в сравнении). Именно такая структура — "стоимость сегмента раскладывается в линейную функцию от переменной запроса" — и есть сигнал, что применим CHT.A concrete example where this transition shape arises naturally: partitioning an array into segments while minimizing total cost, where a segment [j+1, i]'s cost is linear in the right boundary i for a fixed left boundary j — for example, dp[i] = min over j of (dp[j] + (prefix[i]-prefix[j])²), which expands to dp[j] + prefix[i]² - 2·prefix[j]·prefix[i] + prefix[j]² — a linear function of x=prefix[i] with slope -2·prefix[j] and intercept dp[j]+prefix[j]² (the prefix[i]² term is common to every j and drops out of the comparison). Exactly this structure — "segment cost expands into a linear function of the query variable" — is the signal that CHT applies.

D&C-оптимизация применяется в другой ситуации: переход dp[i] = min по j<i от (dp[j] + cost(j,i)) без требования линейности cost, но при условии, что оптимальная точка перехода opt[i] (тот j, на котором достигается минимум) МОНОТОННА по i: opt[i] ≤ opt[i+1] для всех i (формально это следствие так называемого "неравенства четырёхугольника" на cost, но для практического применения достаточно доказать или тщательно проверить саму монотонность). При выполнении этого условия можно вычислять dp для целого диапазона индексов i рекурсией "разделяй и властвуй" (2.4.1 — та же техника, применённая здесь не к самой задаче, а к ускорению перехода ДП): для среднего индекса диапазона ищем его opt перебором только в пределах диапазона, ограниченного найденными opt для границ внешнего вызова, затем рекурсивно обрабатываем левую половину (с верхней границей поиска opt, равной найденному opt среднего) и правую половину (с нижней границей, равной ему же) — на каждом уровне рекурсии суммарный объём переборного поиска по j ограничен O(n), а глубина рекурсии O(log n), что даёт итоговую сложность O(n log n) вместо O(n²).D&C optimization applies in a different setting: the transition dp[i] = min over j<i of (dp[j] + cost(j,i)) with no linearity requirement on cost, but under the condition that the optimal transition point opt[i] (the j that achieves the minimum) is MONOTONIC in i: opt[i] ≤ opt[i+1] for all i (formally a consequence of the so-called "quadrangle inequality" on cost, but for practical purposes it's enough to prove or carefully verify monotonicity itself). Given this condition, dp can be computed for an entire range of indices i via a divide-and-conquer recursion (2.4.1 — the same technique, applied here not to the problem itself but to speeding up a DP transition): for the range's middle index, search for its opt only within the range bounded by the opt values found for the outer call's boundaries, then recursively process the left half (with an upper search bound equal to the middle's found opt) and the right half (with a lower bound equal to the same value) — at each recursion level the total scan work over j is bounded by O(n), and the recursion depth is O(log n), giving a final complexity of O(n log n) instead of O(n²).

// D&C-оптимизация: opt[i] монотонна -> ограничить перебор j диапазоном [optlo, opthi]// D&C optimization: opt[i] monotonic -> bound the j-scan to [optlo, opthi]
void solve(int lo, int hi, int optlo, int opthi,
           std::vector<long long>& dpPrev, std::vector<long long>& dpCur) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    long long best = INF; int bestJ = optlo;
    for (int j = optlo; j <= std::min(mid - 1, opthi); j++) {   // НЕ 0..mid, а [optlo,opthi]// NOT 0..mid, but [optlo,opthi]
        long long cand = dpPrev[j] + cost(j, mid);
        if (cand < best) { best = cand; bestJ = j; }
    }
    dpCur[mid] = best;
    solve(lo, mid - 1, optlo, bestJ, dpPrev, dpCur);      // левая половина: верх. граница = bestJ// left half: upper bound = bestJ
    solve(mid + 1, hi, bestJ, opthi, dpPrev, dpCur);     // правая половина: ниж. граница = bestJ// right half: lower bound = bestJ
}

Честная оговорка сразу: геометрия нижней огибающей линий (CHT) плохо помещается в маленький SVG без искажения сути, поэтому демонстрация ниже показывает не CHT, а D&C-оптимизацию — и не саму геометрию огибающей CHT, а СРАВНЕНИЕ ЧИСЛА ПРОВЕРЯЕМЫХ ПАР (j, i) между наивным полным перебором и D&C-версией на одном и том же небольшом примере (массив из 6 чисел, разбиение на 2 сегмента с квадратичной стоимостью сегмента). При такой малой длине выигрыш в абсолютных числах скромный (например, 17 пар вместо 21) — сама техника рассчитана на большие n, где разница становится решающей (проверено отдельно: при n=128 D&C-версия делает в ~9.6 раза меньше проверок, чем наивная); здесь показан сам механизм отсечения, а не масштаб выигрыша.An honest caveat upfront: the geometry of a line lower envelope (CHT) doesn't fit meaningfully into a small SVG without distorting the substance, so the demo below shows not CHT but D&C optimization — and not the envelope geometry itself, but a COMPARISON OF HOW MANY (j, i) PAIRS GET CHECKED between a naive full scan and the D&C version on the same small example (an array of 6 numbers, partitioned into 2 segments with a quadratic segment cost). At this small size the win in absolute numbers is modest (e.g. 17 pairs instead of 21) — the technique is designed for large n, where the gap becomes decisive (separately verified: at n=128 the D&C version makes about 9.6x fewer checks than the naive one); what's shown here is the pruning mechanism itself, not the scale of the win.