Help in spoj SQRBR dynamic programming problem

Question link link text

-----didn’t get below description and how dp table is made in below link----

Explanation given

This problem can be solved by dynamic programming.

Let count(i,j) be the number of valid ways of filling the first i positions such that there are j more brackets of type ‘[’ than of type ‘]’. Valid ways would mean that it is the prefix of a matched bracket expression and that the locations at which we have enforced ‘[’ brackets have been satisfied. It is easy to see that count(2N,0) is the final answer we need.

The base case of the DP is that count(1,1)=1. You have to fill the first position with a ‘[’ bracket, and there is only way to do this. count(1,i)=0 for i>1.

The recurrence for i>1 is:

count(i,0) = count(i-1,1)
count(i,j) = count(i-1,j-1) + count(i-1,j+1) for j>0

If i is a location where we have enforced a ‘[’ bracket, the recurrence changes to:

count(i,0) = 0
count(i,j) = count(i-1,j-1) for j>0

Using these relations, count(2N,0) can be found in O(N²) time.

solution link of author link text

int f( int i , int sum ){
if( sum less than 0 )return 0;
if( i greater than 2*n ){
if(sum == 0 )return 1; // proper arrangement
return 0;
}
int &Ans = dp[i][sum];
if( Ans != -1 )return Ans;
if( o[i] ){
Ans = f(i+1 , sum+1); // if we are restricted only for [
}
else{
Ans = f(i+1 , sum+1) + f(i+1 , sum-1);// if not put any [ , ]
}
return Ans; // if put [ then add +1 else add -1 , over all sum wil be zero for proper bracket arrangement
}

	for( int i = 0; i < k; i++ ){
		scan num;
		o[num] = 1;
	}
	ans = f(1 , 0);
}

} // hope this will help

1 Like

didn’t get this from author soln

else{

                    if(s.find(i)!=s.end()){


                        dp[i][j] = ((j==0)?0:dp[i-1][j-1]);


                    }else{


                        dp[i][j] = dp[i-1][j+1] + ((j==0)?0:dp[i-1][j-1]);


                    }


                }

please refer to author soln for more detail and link is given.

hey buddy i appreciate ur help but i was looking for the approach for this question and if u could tell it that would be so helpful .
and thanks for help in advance @cenation092.

And more of it i want to understand the given link code so i can be better in making dp table .