Optimal BST - Problem Statement

Given $n$ keys with access frequencies $f_1, \ldots, f_n$, build a BST to reduce expected search cost. If key $i$ is at depth $d_i$, cost is $\sum f_i \cdot (d_i + 1)$. Deeper keys cost more.

This is the problem Knuth designed his improvement for. The interval DP structure comes from the recursive BST definition. Read the problem statement carefully, noting the constraints. Try to identify the recursive structure before looking at the solution.