Divide and conquer optimization: в чём идея и когда её применять?
Есть ДП dp[i][j] = min_{k<=j} (dp[i-1][k] + cost(k, j)) — разбиваю массив на i групп, O(layers · n²). Слышал, что divide-and-conquer optimization снижает до O(layers · n log n). Объясните идею и когда она работает.
2 ответа
D&C optimization работает, когда оптимальная точка перехода монотонна по j: opt[i][j] <= opt[i][j+1], где opt[i][j] — аргмин k для dp[i][j]. Достаточное условие — неравенство четырёхугольника на cost.
Идея: для фиксированного слоя i вычисляем dp[i][*] рекурсивно. Берём середину mid отрезка индексов j, в лоб находим opt[i][mid], перебрав все допустимые k. Из монотонности следует, что для j < mid оптимум лежит в [lo_k, opt[i][mid]], а для j > mid — в [opt[i][mid], hi_k]. Рекурсивно делим обе половины с суженным диапазоном k. Глубина рекурсии log n, на каждом уровне суммарный перебор k это O(n) → O(n log n) на слой.
void solve(int i, int jl, int jr, int kl, int kr) {
if (jl > jr) return;
int jm = (jl + jr) / 2;
long long best = LLONG_MAX; int bestK = kl;
for (int k = kl; k <= min(jm, kr); k++) {
long long v = dp[i-1][k] + cost(k, jm);
if (v < best) { best = v; bestK = k; }
}
dp[i][jm] = best;
solve(i, jl, jm - 1, kl, bestK);
solve(i, jm + 1, jr, bestK, kr);
}
Сложность O(layers · n log n) время. Грабля: верхняя граница k для dp[i][jm] обычно jm (нельзя делить за пределы), поэтому min(jm, kr). И база dp[0][*] должна быть инициализирована до запуска, иначе считаешь из мусора.
Когда выбирать D&C vs CHT vs Кнут: если переход линеен по j (раскладывается в dp[k] + b[k]·x[j]) — бери CHT, он O(n) или O(n log n) без рекурсии. Если cost непростой, но монотонность opt есть, и есть слои (i от 1 до K) — D&C optimization. Если интервальное ДП с двумя половинами dp[i][k]+dp[k+1][j] и QI — Кнут O(n²). D&C удобна тем, что не требует, чтобы cost был линейным: достаточно уметь считать cost(k,j) за O(1) и монотонности оптимума.