Minimum sum possible of any bracket sequence of length N | PHP 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
< ? php $ MAX_VAL = 10000000 ; $ dp = array_fill ( 0 , 100 , array_fill ( 0 , 100 , -1 ) ) ; function find ( $ index , $ openbrk , $ n , $ adj ) { global $ MAX_VAL ; global $ dp ; 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 ] = 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 ] ; } $ n = 4 ; $ adj = array ( array ( 5000 , 3000 ) , array ( 6000 , 2000 ) , array ( 8000 , 1000 ) , array ( 9000 , 6000 ) ) ; echo find ( 1 , 1 , $ n , $ adj ) + $ adj [ 0 ] [ 1 ] ; ? >