Knuth Optimization
Speed up interval DP from O(n^3) to O(n^2) when the optimal split points move monotonically.
Knuth Optimization
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Knuth optimization is the interval-DP speedup for recurrences of the form \[ dp[l][r] = \min_{k \in [l, r-1]} \bigl(dp[l][k] + dp[k+1][r]\bigr) + C(l, r), \] when the best split point moves monotonically with the interval.
When to Use It
Use it when:
the DP is on intervals,
the transition tries every split point,
the cost satisfies the quadrangle-inequality style conditions that imply \[ opt[l][r-1] \le opt[l][r] \le opt[l+1][r]. \]
Core Idea
Instead of searching all split points for every interval, only search between the previously known neighboring optimal split points.
Key Insight
The speedup is not ``because interval DP is nice.'' It is because the argmin drifts slowly. Once you know the optimum split for adjacent intervals, the next optimum is trapped between them.
Worked Problem
Problem.
You have adjacent files with sizes \(a_1, \dots, a_n\). Merging two neighboring groups costs the total size of the merged group. Find the minimum total merge cost.
Why Knuth fits.
The ordinary interval DP is cubic. This cost function satisfies the needed monotonicity, so the split search range can be narrowed to the Knuth interval.
Correctness Intuition
The theorem behind Knuth optimization guarantees the monotone-opt property. Once that is true, searching outside \([opt[l][r-1], opt[l+1][r]]\) cannot improve the answer because the argmin for \([l,r]\) is known to stay inside.
Complexity Analysis
The complexity drops from \(O(n^3)\) to \(O(n^2)\).
Implementation
The sample code solves the adjacent-file merging problem with prefix sums and Knuth's search bounds.
Common Pitfalls
Applying Knuth optimization without proving the monotone-opt condition.
Confusing it with divide-and-conquer DP optimization; the recurrences are different.
Filling intervals in the wrong order and reading
optvalues before they exist.
Variants / Extensions
Optimal BST-style interval DP.
Any interval merge or partition DP with the right quadrangle structure.
Divide-and-conquer optimization when the recurrence is one-sided instead of interval-based.
Practice Problems
File merging with adjacent merges.
Optimal BST-style interval partitioning.
Any interval DP where split-point monotonicity can be proved.
References
Code
Contest-ready reference implementation for the idea explained above.
long long minimum_adjacent_merge_cost(const vector<long long>& a) {
int n = (int)a.size();
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i];
auto range_sum = [&](int l, int r) {
return pref[r + 1] - pref[l];
};
const long long INF = (1LL << 62);
vector<vector<long long>> dp(n, vector<long long>(n, 0));
vector<vector<int>> opt(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) opt[i][i] = i;
for (int len = 2; len <= n; ++len) {
for (int l = 0; l + len - 1 < n; ++l) {
int r = l + len - 1;
dp[l][r] = INF;
int start = opt[l][r - 1];
int finish = opt[l + 1][r];
for (int k = start; k <= finish; ++k) {
long long candidate = dp[l][k] + dp[k + 1][r] + range_sum(l, r);
if (candidate < dp[l][r]) {
dp[l][r] = candidate;
opt[l][r] = k;
}
}
}
}
return dp[0][n - 1];
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.