Optimal Binary Search Tree | DP | A naive recursive implementation of optimal binary search tree problem ; 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
using System ; class GFG { static int sum ( int [ ] freq , int i , int j ) { int s = 0 ; for ( int k = i ; k <= j ; k ++ ) s += freq [ k ] ; return s ; } static int optCost ( int [ ] freq , int i , int j ) { if ( j < i ) return 0 ; if ( j == i ) return freq [ i ] ; int fsum = sum ( freq , i , j ) ; int min = int . MaxValue ; for ( int r = i ; r <= j ; ++ r ) { int cost = optCost ( freq , i , r - 1 ) + optCost ( freq , r + 1 , j ) ; if ( cost < min ) min = cost ; } return min + fsum ; } static int optimalSearchTree ( int [ ] keys , int [ ] freq , int n ) { return optCost ( freq , 0 , n - 1 ) ; } public static void Main ( ) { int [ ] keys = { 10 , 12 , 20 } ; int [ ] freq = { 34 , 8 , 50 } ; int n = keys . Length ; Console . Write ( " Cost ▁ of ▁ Optimal ▁ BST ▁ is ▁ " + optimalSearchTree ( keys , freq , n ) ) ; } }