Balanced expressions such that given positions have opening brackets | Set 2 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  1000 NEW_LINE int find ( int index , int openbrk , int n , int dp [ N ] [ N ] , 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 ] ; } int main ( ) { int dp [ N ] [ N ] ; int n = 2 ; memset ( dp , -1 , sizeof ( dp ) ) ; int adj [ 4 ] = { 1 , 0 , 0 , 0 } ; cout << find ( 0 , 0 , 2 * n , dp , adj ) << endl ; return 0 ; }