Optimal BST - Walkthrough

Build BST with minimum expected search cost. Keys have access frequencies $f_i$. $dp[i][j]$ = min cost for keys $i$ to $j$.

Transition: pick root $k \in [i, j]$. Cost = $dp[i][k-1] + dp[k+1][j] + \sum_{l=i}^{j} f_l$ (depth increases by 1 for all nodes). QI holds for this cost function. Apply Knuth: $opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j]$. Fill by increasing interval length. Each $dp[i][j]$ searches bounded range. Total: $O(n^2)$.