Optimal Binary Search Tree | DP | A utility function to get sum of array elements freq [ i ] to freq [ j ] ; A recursive function to calculate cost of optimal binary search tree ; Base cases no elements in this subarray ; one element in this subarray ; Get sum of freq [ i ] , freq [ i + 1 ] , ... freq [ j ] ; Initialize minimum value ; One by one consider all elements as root and recursively find cost of the BST , compare the cost with min and update min if needed ; Return minimum value ; The main function that calculates minimum cost of a Binary Search Tree . It mainly uses optCost ( ) to find the optimal cost . ; Here array keys [ ] is assumed to be sorted in increasing order . If keys [ ] is not sorted , then add code to sort keys , and rearrange freq [ ] accordingly . ; Driver Code
function sum ( freq , i , j ) { var s = 0 ; for ( var k = i ; k <= j ; k ++ ) s += freq [ k ] ; return s ; } function optCost ( freq , i , j ) { if ( j < i ) return 0 ; if ( j == i ) return freq [ i ] ; var fsum = sum ( freq , i , j ) ; var min = Number . MAX_SAFE_INTEGER ; for ( var r = i ; r <= j ; ++ r ) { var cost = optCost ( freq , i , r - 1 ) + optCost ( freq , r + 1 , j ) ; if ( cost < min ) min = cost ; } return min + fsum ; } function optimalSearchTree ( keys , freq , n ) { return optCost ( freq , 0 , n - 1 ) ; } var keys = [ 10 , 12 , 20 ] ; var freq = [ 34 , 8 , 50 ] ; var n = keys . length ; document . write ( " " + optimalSearchTree ( keys , freq , n ) ) ;