Minimum sum possible of any bracket sequence of length N | C # program to find the Minimum sum possible of any bracket sequence of length N using the given values for brackets ; DP array ; Recursive function to check for correct bracket expression ; / Not a proper bracket expression ; If reaches at end ; / If proper bracket expression ; else if not , return max ; If already visited ; To find out minimum sum ; Driver Code
using System ; class GFG { public static int MAX_VAL = 10000000 ; public static int [ , ] dp = new int [ 100 , 100 ] ; public static int find ( int index , int openbrk , int n , int [ , ] adj ) { if ( openbrk < 0 ) return MAX_VAL ; if ( index == n ) { if ( openbrk == 0 ) { return 0 ; } return MAX_VAL ; } if ( dp [ index , openbrk ] != - 1 ) return dp [ index , openbrk ] ; dp [ index , openbrk ] = Math . Min ( adj [ index , 1 ] + find ( index + 1 , openbrk + 1 , n , adj ) , adj [ index , 0 ] + find ( index + 1 , openbrk - 1 , n , adj ) ) ; return dp [ index , openbrk ] ; } static void Main ( ) { int n = 4 ; int [ , ] adj = new int [ , ] { { 5000 , 3000 } , { 6000 , 2000 } , { 8000 , 1000 } , { 9000 , 6000 } } ; for ( int i = 0 ; i < 100 ; i ++ ) for ( int j = 0 ; j < 100 ; j ++ ) dp [ i , j ] = - 1 ; Console . Write ( find ( 1 , 1 , n , adj ) + adj [ 0 , 1 ] + " STRNEWLINE " ) ; } }