State
dp[i][j] = min cost of BST containing keys i through j.
Advertisement
Transition
Try each key k in [i,j] as root. Cost = left subtree + right subtree + sum of all freqs (each accessed at least once).
dp[i][j] = min over k in [i,j] of
dp[i][k-1] + dp[k+1][j] + prefixSum[j] - prefixSum[i-1];Advertisement
Base case
dp[i][i-1] = 0 (empty range). dp[i][i] = freq[i].
Knuth's optimization
O(N³) → O(N²) via monotonicity of optimal roots. Advanced optimization.