Knuth-Yao 四邊形不等式（Knuth-Yao quadrangle inequality）
/ kuh-NOOTH yow /
像矩陣連乘與最佳二元搜尋樹這類區間動態規劃以 O(n^3) 執行：對 O(n^2) 個區間中的每一個，你掃 O(n) 個分割點。那次掃描常是浪費——較寬區間的最佳分割點接近其子區間的最佳分割點，所以你重新搜尋了已經涵蓋過的地方。Knuth-Yao 四邊形不等式是對成本函數的一個條件，當它成立時，能把每次分割搜尋限制在一個極小的範圍內，把整個動態規劃從 O(n^3) 降到 O(n^2)。
成本函數 w 上的四邊形不等式（QI）說：對所有 a <= b <= c <= d，w(a, c) + w(b, d) <= w(a, d) + w(b, c)。直觀上，「兩個中等勝過一寬一窄」：「交錯」（重疊）的區間頂多和「巢狀」的一樣貴。當動態規劃的成本滿足 QI（以及一個單調性條件）時，可證最佳分割點對兩個引數皆單調：若 opt[i][j] 是區間 [i, j] 的最佳 k，則 opt[i][j-1] <= opt[i][j] <= opt[i+1][j]。那個夾擠就是收穫。你不再在整個 [i, j] 上搜尋 k，而只在 opt[i][j-1] 到 opt[i+1][j] 的範圍內搜尋。在表格上巧妙地求和（按區間長度填表），這些縮小的範圍會彼此抵銷，使動態規劃表的每條對角線總共花 O(n) 而非 O(n^2)，整個動態規劃便成為 O(n^2)。這正是 Knuth 加速最佳 BST 的方式。
所以四邊形不等式是一個辨識器：為你的成本驗證它（常是一個簡短的代數檢查，而本身是區間上求和的權重函數往往滿足它），你就賺到一個免費的 n 因子。它也是分治動態規劃優化的基礎，後者在不同的控制結構中利用同樣的「單調分割」性質。本質的誠實：這是一個你必須真正檢查的充分條件，而非普遍定律。若成本不滿足 QI，最佳分割未必單調，盲目套用 Knuth 的縮窄搜尋會悄悄回傳次佳答案。信任這個加速法之前，請先驗證該不等式（或它所蘊含的單調性）。
最佳 BST 成本 dp[i][j] = W(i,j) + 在 k 上取 dp[i][k-1] + dp[k+1][j] 的最小值。由於權重 W 滿足四邊形不等式，opt[i][j] 落在 opt[i][j-1] 與 opt[i+1][j] 之間。只在那個窄帶內搜尋 k，沿對角線求和，使整張表成為 O(n^2) 而非 O(n^3)。
最佳分割的單調性讓每個區間只在其相鄰區間的最佳分割之間搜尋。
四邊形不等式是一個你必須驗證、而非假設的充分條件。若成本不滿足它，最佳分割可能不單調，而縮窄的搜尋會悄悄回傳錯誤答案。