Optimal binary search tree

JavaView on GFG

Time: O(n^3)

Space: O(n^2)

Intuition

Interval DP. dp[i][j] = minimum cost BST for keys i..j. Cost = sum of frequencies * depth.

Algorithm

1dp[i][j] = min over k in i..j: dp[i][k-1] + dp[k+1][j] + sum(freq[i..j]).
2Build for increasing interval lengths.

Common Pitfalls

•Key insight: adding a root k adds sum(freq[i..j]) to all nodes (depth increases by 1). Use precomputed prefix sums.

Optimal binary search tree.java

Java

// Approach: DP. dp[i][j] = min cost BST for keys[i..j]. Try each key as root and combine sub-costs with freq sum.
// Time: O(n^3) Space: O(n^2)
class Solution {
    public int minCost(int keys[], int freq[]) {
        int n = keys.length;
        int[][] dp = new int[n][n];
        int[][] opt = new int[n][n];
        int[] pre = new int[n + 1];

        for (int i = 0; i < n; i++)
            pre[i + 1] = pre[i] + freq[i];
        for (int i = 0; i < n; i++) {
            dp[i][i] = freq[i];
            opt[i][i] = 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] = Integer.MAX_VALUE;

                int L = opt[i][j - 1];
                int R = opt[i + 1][j];

                for (int k = L; k <= R; k++) {
                    int left = k > i ? dp[i][k - 1] : 0;
                    int right = k < j ? dp[k + 1][j] : 0;
                    int cost = left + right + (pre[j + 1] - pre[i]);
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        opt[i][j] = k;
                    }
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

Was this solution helpful?