Square brackets - MDP

avinashmallik2017 · October 23, 2020, 4:10pm

My code is printing 0 for all test cases please check https://ide.codingblocks.com/s/361191

mr.encoder · October 23, 2020, 4:18pm

Hey @avinashmallik2017 just some side cases which haven’t handled properly, I would suggest you to take reference from here

github.com

marioyc/Online-Judge-Solutions/blob/master/SPOJ/Classical/63 - Square Brackets.cpp

#include <cstdio>
#include <cstring>

using namespace std;

int memo[38][38];
bool open[38];

int solve(int s, int e){
    if(s > e) return 1;
    if(open[e]) return 0;
    if(e == s+1) return 1;
    
    int &ret = memo[s][e];
    
    if(ret == -1){
        ret = 0;
        
        for(int i = s+1;i <= e;i += 2)
            if(!open[i]) ret += solve(s+1,i-1) * solve(i+1,e);

This file has been truncated. show original

And apply it in your code

mr.encoder · October 25, 2020, 6:16pm

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.