Optimal Binary Search Tree | DP | Dynamic Programming C # 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 program to test above functions
using System ; class GFG { static int sum ( int [ ] freq , int i , int j ) { int s = 0 ; for ( int k = i ; k <= j ; k ++ ) { if ( k >= freq . Length ) continue ; s += freq [ k ] ; } return s ; } static int optimalSearchTree ( int [ ] keys , int [ ] freq , int n ) { int [ , ] cost = new int [ n + 1 , n + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) cost [ i , i ] = freq [ i ] ; for ( int L = 2 ; L <= n ; L ++ ) { for ( int i = 0 ; i <= n - L + 1 ; i ++ ) { int j = i + L - 1 ; cost [ i , j ] = int . MaxValue ; for ( int r = i ; r <= j ; r ++ ) { int c = ( ( r > i ) ? cost [ i , r - 1 ] : 0 ) + ( ( r < j ) ? cost [ r + 1 , j ] : 0 ) + sum ( freq , i , j ) ; if ( c < cost [ i , j ] ) cost [ i , j ] = c ; } } } return cost [ 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 ) ) ; } }