Please explain the 3d dp solution for this problem?

#1

Please provide recurrence for 3d dp

#2

Hey @sahazeer123
states can be dp[bracket_idx][opening_brackets_remaining][closing_brackets_remaining]
now recurrence is intuitive.
if current index has to be [ then
dp[i][j][k] = solve(i+1,j-1,k) only if j>0 else there is no way so return 0;
else this idx can be [ or ]
dp[i][j][k] = solve(i+1,j-1,k) // if j>0
dp[i][j][k] += solve(i+1.j,k-1) // if k>0 and j<k so that option is balanced/valid.

#3

for the last case j>k so that option is balance right?

#4

yes it’s to check the balance, but it will be j<k as I choose states as opening_brackets_remaining and closing_brackets_remaining.
so more closed brackets remaining means expression is balanced.

#5

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.