the optimal binary search tree

A binary search tree stores sorted keys so you can look one up by descending from the root, going left for smaller and right for larger. If every key were equally likely to be searched, you would want a perfectly balanced tree to minimize depth. But suppose some keys are searched far more often than others — like a dictionary where 'the' is queried constantly and 'aardvark' almost never. Then it pays to put popular keys near the root even if that unbalances the tree, because a search's cost is how many nodes it visits. The optimal binary search tree is the shape that minimizes the expected (probability-weighted) search cost.

Number the keys 1..n in sorted order, with key i searched with probability (or frequency) f[i]. Let dp[i][j] be the minimum expected cost of an optimal BST built from just keys i..j. Pick which key r in [i, j] becomes the root: its left subtree is the optimal BST on keys i..r-1, its right subtree the optimal BST on keys r+1..j, and choosing r as root pushes every key in i..j one level deeper, adding the whole block's frequency sum W(i, j) = f[i] + ... + f[j] to the cost. So dp[i][j] = W(i, j) + min over r in [i, j] of dp[i][r-1] + dp[r+1][j], with empty ranges costing 0. That extra W(i, j) is the elegant part: you do not have to recompute each key's depth — making r the root simply adds one to everyone's depth, i.e. one copy of the total weight.

Like all interval DP this is O(n^3) time and O(n^2) space in the plain form, and it is the second canonical interval-DP example after matrix chain. Because the cost satisfies the quadrangle inequality, Knuth's optimization restricts the root choice to a shrinking window and brings it down to O(n^2) — historically this is exactly where that speed-up was discovered. A subtlety worth flagging: full treatments also handle unsuccessful searches (keys that fall between stored keys) with dummy leaves and their own probabilities; the bare version above keeps only the successful-search frequencies for clarity.