hdu 1501 Zipper（DP）

dp[i][j]=((dp[i-1][j]&&a[i]==c[i+j]) || (dp[i][j-1]&&b[j]==c[i+j]));

dp[i][j]  表示第一个串的前 i个  和第二个串的前j个能否组成c串的前i+j个。。

注意处理边界因为是从1开始

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

char a[205],b[205],c[405];
int dp[205][205];
int main()
{
    int n;
    int kase=1;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s%s%s",a+1,b+1,c+1);
        a[0]=b[0]=c[0]=‘@‘;


        for(int i=1;i<strlen(a);i++)
        if(a[i]==c[i])dp[i][0]=1;

        for(int i=1;i<strlen(b);i++)
        if(b[i]==c[i])dp[0][i]=1;

        for(int i=1;i<strlen(a);i++)
        {
            for(int j=1;j<strlen(b);j++)
            {
                dp[i][j]=((dp[i-1][j]&&a[i]==c[i+j]) || (dp[i][j-1]&&b[j]==c[i+j]));
            }
        }

        printf("Data set %d: ",kase++);
        if (dp[strlen(a)-1][strlen(b)-1]) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

hdu 1501 Zipper（DP）

原文：http://blog.csdn.net/u010709592/article/details/18863049