DP easy to understand code


#1
bool isposi(string A, string B, string C,int i,int j,int k,vector<bool> &dp) {
    //cout<<i<<' '<<j<<' '<<k<<endl;
    if(dp[k]==true) 
        return true;
    if(i<A.size() and j<B.size() and C[k]==A[i] and C[k]==B[j]) {
        dp[k]=(isposi(A,B,C,i+1,j,k+1,dp) || isposi(A,B,C,i,j+1,k+1,dp));
        return dp[k];
    }
    if(i<A.size() and C[k]==A[i]) {
        dp[k]=isposi(A,B,C,i+1,j,k+1,dp);
        return dp[k];
    }
    if(j<B.size() and C[k]==B[j]) {
        dp[k]=isposi(A,B,C,i,j+1,k+1,dp);
        return dp[k];
    }
    return false;
}
int Solution::isInterleave(string A, string B, string C) {
    if(A.size()+B.size()<C.size())
        return 0;
    else {
        vector<bool> dp(C.size()+1,false);
        dp[C.size()]=true;
        return isposi(A,B,C,0,0,0,dp);
    }
}