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
PepCoding | Optimal Binary Search Tree
Bottom-Up Approach
Optimal Binary Search Tree | DP-24 - GeeksforGeeks
Bottom-Up Approach
https://www.youtube.com/watch?v=vLS-zRCHo-Y&t=11s&ab_channel=AbdulBari
Top-Down Approach
https://www.youtube.com/watch?v=HnslzEs8dbY
DP Bottom Up Approach
// A utility function to get sum of array elements
// freq[i] to freq[j]
int sum(int freq[], int i, int j);
/* A Dynamic Programming based function that calculates
minimum cost of a Binary Search Tree. */
int optimalSearchTree(int keys[], int freq[], int n)
{
/* Create an auxiliary 2D matrix to store results
of subproblems */
int cost[n][n];
/* 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 */
// For a single key, cost is equal to frequency of the key
for (int i = 0; i < n; i++)
cost[i][i] = freq[i];
// Now we need to consider chains of length 2, 3, ... .
// L is chain length.
for (int gap=0; gap<n; gap++)
{
// i is row number in cost[][]
for (int i = 0,j=gap; j < n; i++,j++)
{
cost[i][j] = INT_MAX;
// Try making all keys in interval keys[i..j] as root
for (int r = i; r <= j; r++)
{
// cost of left sub tree when keys[r] becomes root of this subtree
int costofleftsubtree;
if(r==i)
costofleftsubtree = 0; // no left sub tree is present
else
costofleftsubtree = cost[i][r-1];
// cost of right sub tree when keys[r] becomes root of this subtree
int costofrightsubtree;
if(r==j)
costofrightsubtree = 0; // no right sub tree is present
else
costofrightsubtree = cost[r+1][j];
// c = total cost when keys[r] becomes root of this subtree
int c = costofleftsubtree +
costofrightsubtree +
sum(freq, i, j);
// sum(freq, i, j) is added because every search will go through root and
// one comparison will be done for every search.
if (c < cost[i][j])
cost[i][j] = c;
}
}
}
return cost[0][n-1];
}
// A utility function to get sum of array elements
// freq[i] to freq[j]
int sum(int freq[], int i, int j)
{
int s = 0;
for (int k = i; k <= j; k++)
s += freq[k];
return s;
}
// Time Complexity : O(n^4), Space Complexity : O(n^2)
The time complexity of the above solution is O(n^4).
DP Top Down (JAVA)
import java.io.*;
import java.util.*;
public class Main {
private static void optimalbst(int[] keys, int[] frequency, int n) {
int[][]dp = new int[n][n];
for(int gap=0;gap<n;gap++)
{
for(int i=0,j=gap;j<n;j++,i++)
{
if(gap==0)
dp[i][j] = frequency[i];
else if(gap==1)
{
int f1 = frequency[i]+2*frequency[j];//if ith node is root node
int f2 = frequency[j]+2*frequency[i];//if jth node is root node
dp[i][j] = Math.min(f1,f2);
}
else
{
int fs = 0;//sum of frequencies from ith node to jth node
for(int x=i;x<=j;x++)
fs+=frequency[x];
dp[i][j] = Integer.MAX_VALUE;
for(int k=i;k<=j;k++)//assigning k to be the roots of the BSTs
{
int lst = k==i/*if k is leftmost node*/ ? 0 : dp[i][k-1];
int rst = k==j/*if k is rightmost node*/ ? 0 : dp[k+1][j];
dp[i][j] = Math.min(dp[i][j],lst+rst+fs);
}
}
}
}
System.out.println(dp[0][n-1]);
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] keys = new int[n];
int[] frequency = new int[n];
for(int i= 0 ;i < n ; i++) {
keys[i] = scn.nextInt();
}
for(int i = 0 ; i < n; i++){
frequency[i] = scn.nextInt();
}
optimalbst(keys,frequency,n);
}
}
The time complexity of the above solution is O(n^3).