Minimum sum possible of any bracket sequence of length N | Java 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
public class GFG { final static int MAX_VAL = 10000000 ; static int dp [ ] [ ] = new int [ 100 ] [ 100 ] ; 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 ] ; } public static void main ( String args [ ] ) { int n = 4 ; int adj [ ] [ ] = { { 5000 , 3000 } , { 6000 , 2000 } , { 8000 , 1000 } , { 9000 , 6000 } } ; for ( int i = 0 ; i < dp . length ; i ++ ) for ( int j = 0 ; j < dp . length ; j ++ ) dp [ i ] [ j ] = - 1 ; System . out . println ( find ( 1 , 1 , n , adj ) + adj [ 0 ] [ 1 ] ) ; } }