Optimal BST - The DP

$dp[i][j]$ = minimum cost for keys $i$ to $j$. Choose key $k$ as root. Left subtree: $[i, k-1]$. Right subtree: $[k+1, j]$. All keys go one level deeper. $dp[i][j] = \min_{i \leq k \leq j}(dp[i][k-1] + dp[k+1][j]) + \sum_{l=i}^{j} f_l$ The sum adds depth cost for all keys in the range.

Work through examples by hand before coding. Understanding the pattern makes implementation simple. Practice with similar problems to reinforce your understanding.