Doubt in --Brackets All Over

#1

In this question i tried to use dp and i am able to pass 1 test case out of 5 as in other 4 test cases i am getting tle.
pls suggest some method with less time complexity.
link to my code is–https://ide.codingblocks.com/s/77423

#2

This problem can be solved with dynamic programming:

Calculate dp[i, j] : How many sequences of brackets of length i has balance j and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets).

For the given sequence of length n calculate the resulting balance a and the minimum balance b.

Try the length of the sequence added at the beginning c and its balance d. If - b ≤ d then add dp[c, d] × dp[m - n - c, d + a] to the answer.

Time complexity: O((n - m)^2)

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.