xvi. Knuth-Yao Optimization

Interval DPs $d{p}_{i,j}={\min }_{i<k<j}(d{p}_{i,k}+d{p}_{k,j})+w(i,j)$ run in $O(n^2)$ instead of $O(n^3)$ when the optimal split satisfies

${\text{opt}}_{i,j-1}\le {\text{opt}}_{i,j}\le {\text{opt}}_{i+1,j}.$

Yao’s theorem: this holds when $w$ satisfies the quadrangle inequality $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ and is monotone on inclusion, $w(b,c)\le w(a,d)$ for $a\le b\le c\le d$. Merging adjacent piles (cost = range sum) and optimal BST (cost = frequency sum) qualify; matrix chain does not.

template<class W> ll knuth(int n, W w) {                   // half-open intervals [i, j) over 0..n
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1)); vector<vector<int>> opt(n + 1, vector<int>(n + 1));
    for (int i = 0; i < n; i++) opt[i][i + 1] = i;          // length 1 costs 0 here; adjust if leaves cost something
    for (int len = 2; len <= n; len++) for (int i = 0, j = len; j <= n; i++, j++) {
        dp[i][j] = LLONG_MAX;
        for (int k = max(i + 1, opt[i][j - 1]); k <= min(j - 1, opt[i + 1][j]); k++) {
            ll v = dp[i][k] + dp[k][j];
            if (v < dp[i][j]) dp[i][j] = v, opt[i][j] = k;
        }
        dp[i][j] += w(i, j);
    }
    return dp[0][n];
}

Proof: Yao's theorem and the $O(n^2)$ bound

Use the closed form $c(i,i)=0$, $c(i,j)=w(i,j)+{\min }_{i<k\le j}(c(i,k-1)+c(k,j))$ (the half-open code is the same recurrence shifted by one), and write $c_k(i,j)$ for the value of split $k$.
Step 1, $c$ satisfies QI: $c(i,j)+c(i^{\prime },j^{\prime })\le c(i^{\prime },j)+c(i,j^{\prime })$ for $i\le i^{\prime }\le j\le j^{\prime }$, by induction on $j^{\prime }-i$. If $i=i^{\prime }$ or $j=j^{\prime }$ it is an equality.
Case $i<i^{\prime }=j<j^{\prime }$ (needs $c(i,j)+c(j,j^{\prime })\le c(i,j^{\prime })$): let $z$ be optimal for $(i,j^{\prime })$, say $z\le j$ (the case $z>j$ is symmetric). Then $c(i,j)+c(j,j^{\prime })\le w(i,j)+c(i,z-1)+c(z,j)+c(j,j^{\prime })\le w(i,j^{\prime })+c(i,z-1)+c(z,j^{\prime })=c(i,j^{\prime })$, using monotonicity of $w$ and the induction hypothesis $c(z,j)+c(j,j^{\prime })\le c(z,j^{\prime })$ on the shorter interval $[z,j^{\prime }]$.
Case $i<i^{\prime }<j<j^{\prime }$: let $y$ be optimal for $(i^{\prime },j)$ and $z$ for $(i,j^{\prime })$, say $z\le y$ (the other case is symmetric). Then $c(i^{\prime },j^{\prime })+c(i,j)\le c_y(i^{\prime },j^{\prime })+c_z(i,j)=w(i,j)+w(i^{\prime },j^{\prime })+c(i,z-1)+c(i^{\prime },y-1)+c(z,j)+c(y,j^{\prime })$. Apply QI of $w$ to the first two terms and the induction hypothesis $c(z,j)+c(y,j^{\prime })\le c(y,j)+c(z,j^{\prime })$ (valid since $z\le y\le j\le j^{\prime }$ and $j^{\prime }-z<j^{\prime }-i$); regrouping gives $c_z(i,j^{\prime })+c_y(i^{\prime },j)=c(i,j^{\prime })+c(i^{\prime },j)$.
Step 2, monotone argmin: for $i<k\le k^{\prime }\le j$, QI of $c$ on $(i,i+1,k-1,k^{\prime }-1)$, plus the common terms, gives $c_k(i,j)+c_{k^{\prime }}(i+1,j)\le c_{k^{\prime }}(i,j)+c_k(i+1,j)$. Let $K$ be the smallest optimum for $(i,j)$ and $K^{\prime }$ the smallest for $(i+1,j)$, and suppose $K^{\prime }<K$. With $k=K^{\prime }$, $k^{\prime }=K$: $c_{K^{\prime }}(i,j)\le c_K(i,j)+(c_{K^{\prime }}(i+1,j)-c_K(i+1,j))\le c_K(i,j)$, so $K^{\prime }$ is optimal for $(i,j)$ too, contradicting minimality of $K$. Hence ${\text{opt}}_{i,j}\le {\text{opt}}_{i+1,j}$; the inequality ${\text{opt}}_{i,j-1}\le {\text{opt}}_{i,j}$ is symmetric.
Step 3, cost: for a fixed length, the scanned ranges contribute ${\sum }_i({\text{opt}}_{i+1,i+len}-{\text{opt}}_{i,i+len-1}+1)$, which telescopes to $O(n)$. Over $n$ lengths, $O(n^2)$.

Optimal BST

Keys $\mathrm{1..}n$ with access frequencies $p_i$ (and gap frequencies $q_i$ for unsuccessful searches): $e_{i,j}={\min }_{i\le r\le j}(e_{i,r-1}+e_{r+1,j})+W(i,j)$ where $W$ is the total frequency in the range. $W$ is additive (QI with equality) and monotone on inclusion, so Knuth applies and gives Knuth’s original $O(n^2)$ algorithm, with ${\text{root}}_{i,j-1}\le {\text{root}}_{i,j}\le {\text{root}}_{i+1,j}$.

Merging adjacent piles in $O(n\log n)$: Garsia–Wachs

Minimum total cost to merge $n$ piles in a line, each merge costing the merged size (equivalently, an optimal alphabetic binary tree with leaf weights $a_i$, where the cost is $\sum a_i\cdot {\text{depth}}_i$). Hu–Tucker and Garsia–Wachs solve it in $O(n\log n)$; the simple $O(n^2)$ form of Garsia–Wachs is often enough:

ll garsiaWachs(vector<ll> a) {
    const ll INF = LLONG_MAX / 4; ll ans = 0;
    a.insert(a.begin(), INF); a.push_back(INF);
    while (sz(a) > 3) {
        int k = 1; while (a[k - 1] > a[k + 1]) k++;          // leftmost k with a[k-1] <= a[k+1]
        ll t = a[k - 1] + a[k]; ans += t;                     // merge a[k-1], a[k]
        a.erase(a.begin() + k - 1, a.begin() + k + 1);
        int j = k - 1; while (a[j - 1] < t) j--;              // move left past smaller elements
        a.insert(a.begin() + j, t);
    }
    return ans;
}

The result is the optimal cost, but the merge sequence above is not itself a valid sequence of adjacent merges: Garsia–Wachs computes optimal leaf depths, and an alphabetic tree with those depths always exists (it can be built left to right with a stack). This is the classical theorem behind Hu–Tucker; its proof is long (Kingston gives a readable one). If the piles form a circle, the problem needs the $O(n^2)$ Knuth DP on the doubled array.

This is an alphabetic tree problem: unlike Huffman coding, the leaves must stay in their original left-to-right order (so comparing codes compares the original symbols) — that constraint is exactly why plain Huffman’s “merge the two globally smallest weights” is unsound here (the two smallest may not be adjacent), and why a dedicated $O(n\log n)$ algorithm is needed at all. If an $O(n\log n)$ exact answer isn’t actually required, Mehlhorn’s greedy heuristic gets within 2 bits of optimal in $O(n)$.

Applications beyond pile-merging: optimal alphabetic prefix codes, optimal BSTs built from successful-search frequencies only (Knuth’s original motivation), and any code-tree problem where physical/left-to-right ordering is fixed by the application (circuit design, ordered search trees).

Concave vs convex QI, by name: the inequality used above (concave QI) gives a monotone argmin for minimisation; the reversed inequality (convex QI) gives one for maximisation, and is the condition underlying the convex form of CHT and the SMAWK row-minima algorithm. Getting the direction backwards is a common silent bug — always re-check which form your cost satisfies.

Yao’s minimax principle (a separate, equally famous result by the same Yao, unrelated to the interval-DP optimisation beyond sharing an author): the expected cost of the best randomized algorithm against its worst input equals the cost of the best deterministic algorithm against the worst input distribution. This is the standard tool for randomized lower bounds — e.g. proving any randomized comparison sort needs $\Omega (n\log n)$ expected comparisons.

When Knuth does not apply

• Matrix chain: $w$ depends on the split point ($p_i{p}_k{p}_j$), so the theorem doesn’t apply and counterexamples to monotonicity exist; use $O(n^3)$, or Hu–Shing $O(n\log n)$ if really needed.
• Costs that depend on the split in general: try D&C on one endpoint if $d{p}_{i,\cdot }$ rows are Monge, else stay cubic.
• Unverified costs: brute-force check QI and monotonicity on random small instances before trusting the speedup.