string - Kickstart 2017(apac) 模式重叠

Question

我在某些测试用例中得到了不正确的输出，其中我的代码失败了。它对大多数输入都正确运行。这是我的代码问题链接https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p1

int dp[maxn][maxn];
string a,b;
int dprec(int i,int j)
{
    if(i==a.size()&&j==b.size())return 1;
    if(i==a.size()||j==b.size())return 0;
    if(dp[i][j]!=-1)return dp[i][j];
    int& k=dp[i][j];k=0;
    if(a[i]=='*'||b[j]=='*')
    {
        if(a[i]=='*')
        {
            for(int u=0;u<5;u++)
            {
                k|=dprec(i+1,j+u);
            }
        }
        if(b[j]=='*')
        {
            //k|=dprec(i+1,j);
            for(int u=0;u<5;u++)
            {
                k|=dprec(i+u,j+1);
            }
        }
    }
    else
    {
        if(a[i]==b[j])k|=dprec(i+1,j+1);
        else k=0;
    }
    return k;
}
int main()
{
    freopen("inputt.in","r",stdin);
    freopen("result.out","w",stdout);
    int t;cin>>t;
    for(int test=1;test<=t;test++){
        cin>>a>>b;
        memset(dp,-1,sizeof(dp));
        cout<<"Case #"<<test<<": ";
        if(dprec(0,0))cout<<"TRUE"<<endl;
        else cout<<"FALSE"<<endl;
    }
    return 0;
}

Answer 1

很可能是因为 if(i==a.size()||j==b.size()) 当你的'b'完成并且'a'中只剩下'*'时返回 0;

Ps- 我想对此发表评论，但我的声誉还不够。