**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