Optimal Binary Search Tree Construction

Let us assume we somehow have the solution to the question in the last post. How can this solution have come from smaller subproblems?

Our understanding of an optimal BST is a tree with minimum average search cost. How do we find a BST with a minimum cost?

My naive understanding would say let us make all the binary trees we can and then find which of them has the minimum average search cost. The interesting thing to observe here are the overlapping subproblems. If we have found the minimum average cost(C_[1,k]) for a certain binary tree which has it's keys from key1,key2...keyk of the original binary tree and now we attempt to build a binary tree rooted at key(k+1) the average search time for the left subtree would be (C_[1,k]) and the average cost for the right subtree would be C_([k+1,rest of tree]). This is what helps form the main recurrence:


Hokay then! So for every subtree in our huge tree we would have to search for an optimal left subtree and an optimal right subtree by using all possible roots.

Let us try to write a recursive method for the same:
int minAvgCost(int start, int end){
if(start>end)
    return 0;
if(start==end)
    return freq[start];
int min = Integer.MAX_VALUE;
int sumOfSubP = sum(start,end);
for(int i=start;i<=end;i++){
     int temp = sumOfSubP+minAvgCost(start,i-1) +minAvgCost(i+1,end);
     min = min>temp?temp:min;
     }
return min;
} Some Memoization later: int minAvgCost(int start, int end){


if(start>end)
return 0;
if(recArray[start][end]!=-1)
     return recArray[start][end];
if(start==end)
     return freq[start];
 
 int min = Integer.MAX_VALUE;
int sumOfSubP = sum(start,end);

for(int i=start;i<=end;i++){

     int temp = sumOfSubP+minAvgCost(start,i-1) +minAvgCost(i+1,end);
     min = min>temp?temp:min;
     }

recArray[start][end] = min;
return min;
}