The Best Search Tree for These Keys
Keys 1..n are given in SORTED order, each with a search frequency. Build a binary search
tree over them. A key at depth d, counting the root as depth 1, costs frequency * d to
search.
Print the smallest total cost over all binary search trees.
frequencies 34 8 50 -> 142
frequencies 10 12 -> 32
## Why the most frequent key is not always the root
Putting the highest-frequency key at the root is the obvious rule and it is wrong: doing so can force a very unbalanced tree that pushes many other keys deep.
100 1 1 answers 105 and 1 1 100 also answers 105, both by rooting at the heavy key,
which happens to be right there. 4 2 6 3 answers 26, and checking by hand which key is at
the root is the fastest way to see the rule fail.
## The state, and why a BST forces an interval
A binary search tree over sorted keys has a crucial property: the left subtree of any node holds a CONTIGUOUS run of keys before it, and the right subtree a contiguous run after.
So a subtree is always an interval of the key array, never a scattered set. That is what makes this an interval DP rather than a subset one, and it is the same structural fact that makes matrix chain multiplication work.
dp[i][j] = the smallest cost of a BST over keys i..j, with its root at depth 1
## The recurrence, and the depth trick
Choosing key r as the root of i..j:
dp[i][j] = min over r of dp[i][r-1] + dp[r+1][j] + sum of frequencies over i..j
The additive term is the whole point. Making r the root pushes EVERY key in the range one
level deeper than it would be in its own subtree, and each key contributes its frequency
once per level.
So instead of tracking depths explicitly, add the range's total frequency once per level of nesting. The sum telescopes into exactly the depth-weighted cost.
That reframing is why this problem is tractable at all: a depth-indexed state would need a third dimension.
## The frequency sum must be a prefix sum
The additive term is needed for every (i, j), so precompute prefix sums and read it in
O(1). Recomputing it inside the loop adds a factor of n for nothing.
## Boundaries
A single key answers its own frequency, since it is the root at depth 1. 1 answers 1.
1 1 1 answers 5: a balanced tree costs 1*1 + 1*2 + 1*2 = 5, and any chain costs 6.
5 5 5 5 answers 40, four equal keys where balance is all that matters.
## Cost
Time O(n^3). Space O(n^2).
Knuth's optimisation reduces it to O(n^2) by bounding the root search between the optimal
roots of two smaller ranges. It is worth knowing it exists and is rarely the expected answer.