Optimal Search Tree — Solution & Editorial

Back to the Problem

Interval DP choosing the root of each key-range: dp[i][j] = min over root k of dp[i][k−1] + dp[k+1][j], plus the range's total frequency (every key sinks one level deeper). Knuth's optimization drops it to O(N²).

Complexity: O(N³)