the Knuth-Yao quadrangle inequality
/ kuh-NOOTH yow /
Interval DPs like matrix-chain and the optimal binary search tree run in O(n^3): for each of the O(n^2) intervals you scan O(n) split points. Often that scan is wasteful — the best split point for a wider interval is close to the best split points of its sub-intervals, so you re-search ground you have already covered. The Knuth-Yao quadrangle inequality is a condition on the cost function that, when it holds, lets you restrict each split search to a tiny range, dropping the whole DP from O(n^3) to O(n^2).
The quadrangle inequality (QI) on a cost function w says: for all a <= b <= c <= d, w(a, c) + w(b, d) <= w(a, d) + w(b, c). Intuitively, two-medium beats wider-and-narrower: 'crossing' (overlapping) intervals cost at most as much as 'nested' ones. When the DP's cost satisfies QI (and a monotonicity condition), one can prove the optimal split point is monotone in both arguments: if opt[i][j] is the best k for interval [i, j], then opt[i][j-1] <= opt[i][j] <= opt[i+1][j]. That sandwich is the payoff. Instead of searching k over all of [i, j], you search only the range from opt[i][j-1] to opt[i+1][j]. Summed cleverly over the table (filling by interval length), these shrunken ranges telescope so that each diagonal of the DP table costs O(n) total rather than O(n^2), and the whole DP becomes O(n^2). This is exactly how Knuth sped up the optimal BST.
So the quadrangle inequality is a recognizer: verify it for your cost (often a short algebraic check, and weight functions that are themselves sums over intervals frequently satisfy it), and you earn a free factor of n. It also underlies the divide-and-conquer DP optimization, which exploits the same monotone-split property in a different control structure. The essential honesty: this is a sufficient condition you must actually check, not a universal law. If the cost does not satisfy QI, the optimal split need not be monotone, and blindly applying Knuth's narrowed search will quietly return suboptimal answers. Verify the inequality (or the monotonicity it implies) before trusting the speed-up.
Optimal BST cost dp[i][j] = W(i,j) + min over k of dp[i][k-1] + dp[k+1][j]. Because the weight W satisfies the quadrangle inequality, opt[i][j] lies between opt[i][j-1] and opt[i+1][j]. Searching k only in that narrow band, summed over the diagonal, makes the whole table O(n^2) instead of O(n^3).
Monotone optimal splits let each interval search only between its neighbours' optima.
The quadrangle inequality is a sufficient condition you must verify, not assume. If the cost does not satisfy it, the optimal split may not be monotone, and the narrowed search silently returns wrong answers.