Question link link text
-----didn’t get below description and how dp table is made in below link----
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