Оптимизация Кнута: для каких ДП работает и какое условие надо проверить?
Есть интервальное ДП вида dp[i][j] = min_{i<=k<j} (dp[i][k] + dp[k+1][j]) + cost(i,j) — это O(n³). Говорят, оптимизация Кнута ускоряет до O(n²). Когда она применима и как именно ускоряет?
2 ответа
Оптимизация Кнута (Knuth / Knuth-Yao) применима к интервальным ДП вида dp[i][j] = cost(i,j) + min_{i<=k<j}(dp[i][k] + dp[k+1][j]), если cost удовлетворяет двум условиям:
- Неравенство четырёхугольника (QI):
cost(a,c) + cost(b,d) <= cost(a,d) + cost(b,c)дляa<=b<=c<=d. - Монотонность:
cost(b,c) <= cost(a,d)дляa<=b<=c<=d.
Когда они выполнены, оптимальная точка деления opt[i][j] монотонна: opt[i][j-1] <= opt[i][j] <= opt[i+1][j]. Значит для каждой (i,j) перебираешь k не от i до j, а только в суженном окне [opt[i][j-1], opt[i+1][j]]. Суммарно работа по всем интервалам одной длины телескопируется в O(n), всего O(n²).
for (int i = 0; i < n; i++) { dp[i][i] = 0; opt[i][i] = i; }
for (int len = 2; len <= n; len++)
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = LLONG_MAX;
for (int k = opt[i][j-1]; k <= min(j-1, opt[i+1][j]); k++) {
long long v = dp[i][k] + dp[k+1][j] + cost(i, j);
if (v < dp[i][j]) { dp[i][j] = v; opt[i][j] = k; }
}
}
Сложность O(n²) время, O(n²) память. Классические применения: оптимальное бинарное дерево поиска, склейка файлов (optimal file merging). Грабля: если QI не выполнено — opt не монотонен, окно неверно, получишь WA; обязательно проверь cost перед применением.
Полезная практическая проверка: если cost(i,j) — это сумма на отрезке (например, prefix[j+1]-prefix[i]), то неравенство четырёхугольника для неё выполняется автоматически (для неотрицательных весов), и Кнут применим без раздумий. Это покрывает большинство задач на «оптимальное слияние/разбиение». Не путай оптимизацию Кнута с divide-and-conquer optimization: D&C тоже опирается на монотонность opt, но для перехода dp[i][j] = min_k(dp[i-1][k] + cost(k,j)) (один свободный индекс деления), а Кнут — для двумерного интервального с двумя зависимостями dp[i][k] и dp[k+1][j].