Yao Optimization

Purpose: Andrew Yao’s 1980 theorem giving the precise conditions under which the optimal split point of an interval DP is monotone — the theoretical foundation that licenses Knuth optimization.

The Theorem

Consider

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

Yao’s conditions. If the weight function $w$ satisfies

1. Quadrangle inequality (QI):
   $w(a,c)+w(b,d)\le w(a,d)+w(b,c)\forall a\le b\le c\le d;$
2. Monotonicity on intervals:
   $w(b,c)\le w(a,d)\forall a\le b\le c\le d;$

then $dp$ itself satisfies the quadrangle inequality, and the argmin is monotone:

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

That monotonicity is precisely what reduces the $O(n^3)$ DP to $O(n^2)$.

Why this matters

It converts “I noticed the optimum seems monotone” into a checkable criterion. If you can verify QI and interval monotonicity for your cost function, the speedup is guaranteed correct. If you cannot, the speedup may silently produce wrong answers on some inputs — which is far worse than being slow.

Verifying QI in practice

Write a brute-force checker before trusting the optimization:

bool checkQI(int n, function<long long(int,int)> w) {
    for (int a = 0; a < n; a++)
      for (int b = a; b < n; b++)
        for (int c = b; c < n; c++)
          for (int d = c; d < n; d++)
            if (w(a,c) + w(b,d) > w(a,d) + w(b,c)) return false;
    return true;
}

Run it on $n\le 20$ with random weights. Thirty seconds of checking saves an hour of debugging a wrong-answer verdict.

Cost functions that satisfy QI

$w(i,j)$	QI?
${\sum }_{k=i}^j{a}_k$ with $a_k\ge 0$ (range sum)	yes
$(\text{range sum}{)}^2$	yes
${\max }_{i\le k\le j}{a}_k$	yes
number of distinct values in $[i,j]$	yes
$\log (\text{range sum})$	yes (concave of a Monge function)
$p_i\cdot p_k\cdot p_j$ (matrix chain)	no — stays $O(n^3)$

Concave vs convex

Two dual forms appear in the literature:

• Concave QI ($w(a,c)+w(b,d)\le w(a,d)+w(b,c)$) — used above, gives monotone argmin for minimisation;
• Convex QI (inequality reversed) — gives monotone argmin for maximisation, and drives the convex form of CHT and the SMAWK variants.

Getting the direction wrong is the second most common source of bugs here, after failing to check the condition at all.

Related results by Yao

Yao also proved Yao’s minimax principle: the expected cost of the best randomized algorithm on the worst input equals the cost of the best deterministic algorithm on the worst input distribution. It is the standard tool for proving randomized lower bounds — e.g. that any randomized comparison sort needs $\Omega (n\log n)$ expected comparisons.

Variants / Use Cases

• Knuth Optimization — the algorithm this theorem justifies
• SMAWK — the $O(n)$ row-minima algorithm for totally monotone matrices
• Divide and Conquer DP — needs only argmin monotonicity, a weaker condition
• Interval DP — where these optimizations apply