Boolean Parenthesization (DP) (Help)

Правка en2, от Garvit_2013, 2021-08-11 16:59:57

Can anybody tell me why my code is incorrect?

Thanks in advance.

Question link: https://practice.geeksforgeeks.org/problems/boolean-parenthesization5610/1

int solve(int i,int j, string &s,  vector<vector<vector<int>>> &v,bool flag)
{
 
    if(i==j)
    {
        if(flag)
        return s[i]=='T';
        else
         return s[i]=='F';
    }
    if(v[i][j][flag]==-1)
    {
        
        int ans=0;
        if(flag)
        {
            for(int k=i+1;k<j;k=k+2)
    {
        if(s[k]=='&')
        {
            ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,flag);
        }
        else if(s[k]=='|')
        {
             ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,!flag);
             ans+= solve(i,k-1,s,v,!flag)*solve(k+1,j,s,v,flag);
             ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,flag);
        }
        else
        {
             ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,!flag);
             ans+= solve(i,k-1,s,v,!flag)*solve(k+1,j,s,v,flag);
        }
       
    }
        }
        else
        {
            for(int k=i+1;k<j;k=k+2)
    {
        if(s[k]=='&')
        {
             ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,flag);
             ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,!flag);
             ans+= solve(i,k-1,s,v,!flag)*solve(k+1,j,s,v,flag);
        }
        else if(s[k]=='|')
        {
             ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,flag);
        }
        else
        {
             ans+= solve(i,k-1,s,v,flag)*solve(k+1,j,s,v,flag);
             ans+= solve(i,k-1,s,v,!flag)*solve(k+1,j,s,v,!flag);
        }
       
    }
    }
     v[i][j][flag]=ans;
}
      return v[i][j][flag];
}

class Solution{
public:
    int countWays(int N, string S){
        // code here
        //cout<<S.size();
        vector<vector<vector<int>>> v(N,vector<vector<int>> (N,vector<int> (2,-1)));
        return solve(0,N-1,S,v,true);
    }
};
Теги #help, #dynamic programing, #geeksforgeeks

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Garvit_2013 2021-08-11 20:07:35 9
en2 Английский Garvit_2013 2021-08-11 16:59:57 8
en1 Английский Garvit_2013 2021-08-11 16:58:52 2112 Initial revision (published)