Optimal Binary Search Tree

Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

Let us first define the cost of a BST. The cost of a BST node is level of that node multiplied by its frequency. Level of root is 1.

Examples:

Input:  keys[] = {10, 12}, freq[] = {34, 50}
There can be following two possible BSTs 
        10                       12
          \                     / 
           12                 10
          I                     II
Frequency of searches of 10 and 12 are 34 and 50 respectively.
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118 


Input:  keys[] = {10, 12, 20}, freq[] = {34, 8, 50}
There can be following possible BSTs
    10                12                 20         10              20
      \             /    \              /             \            /
      12          10     20           12               20         10  
        \                            /                 /           \
         20                        10                12             12  
     I               II             III             IV             V
Among all possible BSTs, cost of the fifth BST is minimum.  
Cost of the fifth BST is 1*50 + 2*34 + 3*8 = 142

class solution {
    // Here array keys[] is assumed to be sorted in
    // increasing order. This means when we make left and right fn calls then the
    // keys will be in correct places (as they are already sorted)
    // If keys[] is not sorted, then
    // add code to sort keys, and rearrange freq[] accordingly.
    public static int optimalSearchTree(int[] keys, int[] freq, int n) {

        int[][] cost = new int[n][n];
        // Stores sum of frequency array between i & j
        int[][] prefixSum = new int[n][n];
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += freq[j];
                prefixSum[i][j] = sum;
            }
        }
        /*
         * cost[i][j] = Optimal cost of binary search tree that can be formed from
         * keys[i] to keys[j]. cost[0][n-1] will store the resultant cost
         */
        // i and j are start and end pointers between which we are working
        // Base case when i=j
        for (int i = 0; i < n; i++)
            cost[i][i] = freq[i];
        // Diagonal base case
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                cost[i][j] = Integer.MAX_VALUE;
                // Consider all the elements in between as root node
                for (int r = i; r <= j; r++) {
                    // Adding additional layer of prefixSum, because all the node in left and right subtree
                    // will be at a lower level in this tree, therefore their multiplier increases by 1
                    cost[i][j] = Math.min(cost[i][j], (r > i ? cost[i][r - 1] : 0) + (r < j ? cost[r + 1][j] : 0) + prefixSum[i][j]);
                }
            }
        }
        return cost[0][n - 1];
    }
}