1010. Zipper

TAG 动态规划 dp

使3个字符串A B C

dp[i][j]表示A的前i个字符和B的前j个字符能否组合成C的前i+j个字符

状态转移方程：

dp[i][j]= dp[i-1][j] && C[i+j-1]==A[i-1] || dp[i][j-1] && C[i+j-1]==B[j-1]; //注意边界

/* source code of submission 419888, Zhongshan University Online Judge System */
#include <stdio.h>
#include <memory.h>
#include <string.h>
bool dp[201][201];
char A[201],B[201],C[401];
int T,n;
int len;
int main(int argc, char *argv[])
{
    scanf("%d", &T);
    n=0;
    while ( n<T )
    {
        scanf("%s%s%s", A, B, C);
        memset(dp, false, sizeof(dp) );
        dp[0][0]=true;
        len=strlen(A);
        for (int i=0; i<=len; ++i)
        {
            for (int j=0; j<=len; ++j)
            {
                if ( i+j==0 )
                {
                    continue;
                }
                if ( i==0 )
                {
                   dp[0][j]=dp[0][j-1] && C[j-1]==B[j-1];
                }
                else if ( j==0 )
                {
                   dp[i][0]=dp[i-1][0] && C[i-1]==A[i-1];
                }
                else
                {
                   dp[i][j]=    dp[i-1][j] && C[i+j-1]==A[i-1]
                             || dp[i][j-1] && C[i+j-1]==B[j-1];
                }
                //printf("%d", dp[i][j]);
                
            }
//printf("/n");
        }
        printf("Data set %d: %s/n",++n, dp[len][len]? "yes": "no" );
    }
    return 0;