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];
}
}