最佳二元搜尋樹（optimal binary search tree）

二元搜尋樹把已排序的鍵存起來，讓你從根往下走來查找——較小往左、較大往右。若每個鍵被查的機率相同，你會想要一棵完美平衡的樹以最小化深度。但假設某些鍵被查的次數遠多於其他鍵——像字典裡「the」被不斷查詢、而「aardvark」幾乎沒人查。那麼即使會讓樹失衡，把熱門的鍵放在靠近根處也划算，因為一次搜尋的成本就是它走過的節點數。最佳二元搜尋樹就是使期望（以機率加權）搜尋成本最小的那個形狀。

把鍵依排序編號為 1..n，鍵 i 被查的機率（或頻率）為 f[i]。令 dp[i][j] 為僅由鍵 i..j 構成的最佳 BST 的最小期望成本。挑哪個鍵 r（在 [i, j] 中）當根：它的左子樹是鍵 i..r-1 上的最佳 BST，右子樹是鍵 r+1..j 上的最佳 BST，而選 r 當根會把 i..j 中每個鍵都往下推一層，使成本加上整塊的頻率總和 W(i, j) = f[i] + ... + f[j]。於是 dp[i][j] = W(i, j) + 在 r 屬於 [i, j] 上取 dp[i][r-1] + dp[r+1][j] 的最小值，空區間成本為 0。那多出來的 W(i, j) 正是精妙之處：你不必重算每個鍵的深度——讓 r 當根只是把所有人的深度加一，也就是加上一份總權重。

如同所有區間動態規劃，樸素形式為 O(n^3) 時間、O(n^2) 空間，這是繼矩陣連乘之後第二個經典區間DP範例。由於成本滿足四邊形不等式，Knuth 的優化把根的選擇限制在一個逐步收縮的窗口內，將其降到 O(n^2)——歷史上這正是該加速法被發現的地方。一個值得指出的細節：完整處理還會用虛擬葉子與它們自己的機率來涵蓋失敗搜尋（落在已存鍵之間的鍵）；上面的精簡版為求清楚只保留成功搜尋的頻率。