Optimal Binary Search Tree | DP | A utility function to get sum of array elements freq [ i ] to freq [ j ] ; A Dynamic Programming based function that calculates minimum cost of a Binary Search Tree . ; Create an auxiliary 2D matrix to store results of subproblems ; For a single key , cost is equal to frequency of the key ; Now we need to consider chains of length 2 , 3 , ... . L is chain length . ; i is row number in cost [ ] [ ] ; Get column number j from row number i and chain length L ; Try making all keys in interval keys [ i . . j ] as root ; c = cost when keys [ r ] becomes root of this subtree ; Driver program to test above functions
function sum ( freq , i , j ) { var s = 0 ; for ( var k = i ; k <= j ; k ++ ) s += freq [ k ] ; return s ; } function optimalSearchTree ( keys , freq , n ) { var cost = new Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) cost [ i ] = new Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) cost [ i ] [ i ] = freq [ i ] ; for ( var L = 2 ; L <= n ; L ++ ) { for ( var i = 0 ; i <= n - L + 1 ; i ++ ) { var j = i + L - 1 ; if ( i >= n j >= n ) break cost [ i ] [ j ] = Number . MAX_SAFE_INTEGER ; for ( var r = i ; r <= j ; r ++ ) { var c = 0 ; if ( r > i ) c += cost [ i ] [ r - 1 ] if ( r < j ) c += cost [ r + 1 ] [ j ] c += sum ( freq , i , j ) ; if ( c < cost [ i ] [ j ] ) cost [ i ] [ j ] = c ; } } } return cost [ 0 ] [ n - 1 ] ; } var keys = [ 10 , 12 , 20 ] ; var freq = [ 34 , 8 , 50 ] ; var n = keys . length ; document . write ( " " + optimalSearchTree ( keys , freq , n ) ) ;