Balanced expressions such that given positions have opening brackets | Set 2 | Function to find Number of proper bracket expressions ; If open - closed brackets < 0 ; If index reaches the end of expression ; If brackets are balanced ; If already stored in dp ; If the current index has assigned open bracket ; Move forward increasing the length of open brackets ; Move forward by inserting open as well as closed brackets on that index ; return the answer ; DP array to precompute the answer ; Open brackets at position 1 ; Calling the find function to calculate the answer
< ? php function find ( $ index , $ openbrk , $ n , & $ dp , & $ adj ) { if ( $ openbrk < 0 ) return 0 ; if ( $ index == $ n ) { if ( $ openbrk == 0 ) return 1 ; else return 0 ; } if ( $ dp [ $ index ] [ $ openbrk ] != -1 ) return $ dp [ $ index ] [ $ openbrk ] ; if ( $ adj [ $ index ] == 1 ) { $ dp [ $ index ] [ $ openbrk ] = find ( $ index + 1 , $ openbrk + 1 , $ n , $ dp , $ adj ) ; } else { $ dp [ $ index ] [ $ openbrk ] = find ( $ index + 1 , $ openbrk + 1 , $ n , $ dp , $ adj ) + find ( $ index + 1 , $ openbrk - 1 , $ n , $ dp , $ adj ) ; } return $ dp [ $ index ] [ $ openbrk ] ; } $ N = 1000 ; $ dp = array ( array ( ) ) ; $ n = 2 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { for ( $ j = 0 ; $ j < $ N ; $ j ++ ) { $ dp [ $ i ] [ $ j ] = -1 ; } } $ adj = array ( 1 , 0 , 0 , 0 ) ; echo find ( 0 , 0 , 2 * $ n , $ dp , $ adj ) . " STRNEWLINE " ; ? >