DP states?! This problem is solved using a very stupid greedy algo.

Oh, I understand it's a bit more difficult.

Seems that in order to make some bracket sequence regular, you have 4 different choices:

1. If the first and the last brackets of the sequence are of the same type and match each other (I mean: the first is opening and the last is closing), you can just throw them away and make the remaining subsequence regular.
2. If the first bracket is opening, you can append a closing bracket to the end, throw both away and go to the remainder.
3. If the last bracket is closing, the case will be symmetrical to case 2.
4. You can split the sequence into two non-zero sized parts and make both regular.

These ideas give an O(N^3) DP solution.

Thanks