Given sorted keys and their access probabilities, Optimal BST DP chooses roots over intervals to minimize expected search cost. Interval DP with prefix sums yields O(n^3) time and O(n^2) space.
int optimalBST(vector<int>& freq) {
int n = freq.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
vector<int> pref(n + 1, 0);
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + freq[i];
for (int i = 0; i < n; i++) dp[i][i] = freq[i];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
int sum = pref[j + 1] - pref[i];
for (int r = i; r <= j; r++) {
int left = r > i ? dp[i][r - 1] : 0;
int right = r < j ? dp[r + 1][j] : 0;
dp[i][j] = min(dp[i][j], left + right + sum);
}
}
}
return dp[0][n - 1];
}For keys i..j, choose root r that minimizes left + right + sum(freq[i..j]).
Higher-frequency keys should be nearer root to reduce weighted depth.
Compute by increasing interval length.
Quiz coming soon for this algorithm.