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
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 optCost ( freq , i , j ) : NEW_LINE INDENT if j < i : NEW_LINE INDENT return 0 NEW_LINE DEDENT if j == i : NEW_LINE INDENT return freq [ i ] NEW_LINE DEDENT fsum = Sum ( freq , i , j ) NEW_LINE Min = 999999999999 NEW_LINE for r in range ( i , j + 1 ) : NEW_LINE INDENT cost = ( optCost ( freq , i , r - 1 ) + optCost ( freq , r + 1 , j ) ) NEW_LINE if cost < Min : NEW_LINE INDENT Min = cost NEW_LINE DEDENT DEDENT return Min + fsum NEW_LINE DEDENT def optimalSearchTree ( keys , freq , n ) : NEW_LINE INDENT return optCost ( freq , 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