Optimal Binary Search Tree | DP | Dynamic Programming code for Optimal Binary Search Tree Problem ; 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 Code
INT_MAX = 2147483647 NEW_LINE def sum ( freq , i , j ) : NEW_LINE INDENT s = 0 NEW_LINE for k in range ( i , j + 1 ) : NEW_LINE INDENT s += freq [ k ] NEW_LINE DEDENT return s NEW_LINE DEDENT def optimalSearchTree ( keys , freq , n ) : NEW_LINE INDENT cost = [ [ 0 for x in range ( n ) ] for y in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT cost [ i ] [ i ] = freq [ i ] NEW_LINE DEDENT for L in range ( 2 , n + 1 ) : NEW_LINE INDENT for i in range ( n - L + 2 ) : NEW_LINE INDENT j = i + L - 1 NEW_LINE if i >= n or j >= n : NEW_LINE INDENT break NEW_LINE DEDENT cost [ i ] [ j ] = INT_MAX NEW_LINE for r in range ( i , j + 1 ) : NEW_LINE INDENT c = 0 NEW_LINE if ( r > i ) : NEW_LINE INDENT c += cost [ i ] [ r - 1 ] NEW_LINE DEDENT if ( r < j ) : NEW_LINE INDENT c += cost [ r + 1 ] [ j ] NEW_LINE DEDENT c += sum ( freq , i , j ) NEW_LINE if ( c < cost [ i ] [ j ] ) : NEW_LINE INDENT cost [ i ] [ j ] = c NEW_LINE DEDENT DEDENT DEDENT DEDENT return cost [ 0 ] [ n - 1 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT keys = [ 10 , 12 , 20 ] NEW_LINE freq = [ 34 , 8 , 50 ] NEW_LINE n = len ( keys ) NEW_LINE print ( " Cost ▁ of ▁ Optimal ▁ BST ▁ is " , optimalSearchTree ( keys , freq , n ) ) NEW_LINE DEDENT