Knuth Optimization

Purpose: Reduce an interval DP of the form

$dp[i][j]={\min }_{i<k<j}(dp[i][k]+dp[k][j])+C(i,j)$

from $O(n^3)$ to $O(n^2)$, by restricting the search for the optimal split point.

The Condition

Let $\mathrm{opt}[i][j]$ be the smallest $k$ achieving the minimum. Knuth’s optimization applies when

$\mathrm{opt}[i][j-1]\le \mathrm{opt}[i][j]\le \mathrm{opt}[i+1][j].$

This monotonicity is guaranteed when the cost function $C$ satisfies both:

1. Quadrangle inequality (QI): $C(a,c)+C(b,d)\le C(a,d)+C(b,c)$ for all $a\le b\le c\le d$.
2. Monotonicity on the lattice of intervals: $C(b,c)\le C(a,d)$ whenever $a\le b\le c\le d$.

In practice, most “merge two adjacent piles, cost = sum of the range” problems satisfy both, and you can verify them by brute force on small $n$ before committing.

Algorithm

Iterate by increasing interval length. For each $(i,j)$, scan $k$ only in $[\mathrm{opt}[i][j-1],\mathrm{opt}[i+1][j]]$ and record the argmin.

Code

// dp[i][j] over half-open intervals; C(i,j) is the merge cost
long long solve(int n, function<long long(int,int)> C) {
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    vector<vector<int>> opt(n + 1, vector<int>(n + 1, 0));
 
    for (int i = 0; i < n; i++) opt[i][i + 1] = i;
 
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len;
            dp[i][j] = LLONG_MAX;
            int lo = opt[i][j - 1], hi = opt[i + 1][j];
            for (int k = lo; k <= hi; k++) {
                long long cur = dp[i][k] + dp[k][j] + C(i, j);
                if (cur < dp[i][j]) { dp[i][j] = cur; opt[i][j] = k; }
            }
        }
    }
    return dp[0][n];
}

Paradigm

Dynamic programming with a monotone argmin. The same family as divide and conquer DP and SMAWK — all exploit the quadrangle inequality, just with different access patterns.

Complexity

• Time: $O(n^2)$
• Space: $O(n^2)$

The telescoping argument: for a fixed interval length, the total work is
${\sum }_i(\mathrm{opt}[i+1][j]-\mathrm{opt}[i][j-1]+1),$
and the $\mathrm{opt}$ terms telescope across $i$, leaving $O(n)$ per length and $O(n^2)$ overall.

Classic Applications

• Optimal binary search tree (Knuth’s original problem) — the reason it is named after him
• Merging stones / “burning piles” — merge adjacent piles, cost = sum of the merged range
• Optimal file merging, matrix chain-like problems with QI costs
• Hu-Tucker — the $O(n\log n)$ alternative for the alphabetic-tree case

When it does not apply

Matrix chain multiplication does not satisfy the quadrangle inequality in general, so it stays $O(n^3)$. Always test QI on random small inputs before assuming.

Related Optimizations

Recurrence shape	Technique	Result
$dp[i][j]={\min }_{k}dp[i][k]+dp[k][j]+C(i,j)$, QI	Knuth	$O(n^2)$
$dp[i][j]={\min }_{k}dp[i-1][k]+C(k,j)$, monotone opt	D&C DP	$O(kn\log n)$
Row minima of a totally monotone matrix	SMAWK	$O(n)$
$dp[i]={\min }_j(dp[j]+b_j{x}_i)$	CHT	$O(n)$ / $O(n\log n)$
Fixed-width window minimum	Monotone queue	$O(n)$