Balanced expressions such that given positions have opening brackets | Set 2 | Java implementation of above approach using memoization ; 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 ; Driver code ; DP array to precompute the answer ; Open brackets at position 1 ; Calling the find function to calculate the answer
public class GFG { static final int N = 1000 ; static int find ( int index , int openbrk , int n , int dp [ ] [ ] , int 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 ] ; } public static void main ( String [ ] args ) { int dp [ ] [ ] = new int [ N ] [ N ] ; int n = 2 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } int adj [ ] = { 1 , 0 , 0 , 0 } ; System . out . print ( find ( 0 , 0 , 2 * n , dp , adj ) ) ; } }