#include<stdio.h>
#include<string.h>
int f[205][205];
char s1[205],s2[205],s3[420];
int dp(int i,int j)
{
  if(f[i][j]!=-1)
    return f[i][j];//记忆化 
  if(i==0&&j==0)
    return f[i][j]=1;//当2字符串所有字符都匹配 
  if(i>0&&s3[i+j]==s1[i])//如果第1个字符串的的第i个字符和第3个字符串的第i+j的字符匹配    
  {
     if(dp(i-1,j))
       return f[i][j]=1;
  }
  if(j>0&&s3[i+j]==s2[j])//如果第2个字符串的第j个字符和第3个字符串的第i+j的字符匹配 
  {
     if(dp(i,j-1))
       return f[i][j]=1;
  }
  return f[i][j]=0;     
}
int main()
{
  int n,len1,len2,len3;
  scanf("%d",&n);
  for(int t=1;t<=n;t++)
  {
    scanf("%s %s %s",s1+1,s2+1,s3+1);
    s1[0]=' ';
    s2[0]=' ';
    s3[0]=' ';
    len3=strlen(s3);
    len2=strlen(s2);
    len1=strlen(s1);
    memset(f,-1,sizeof(f));
    int c=dp(len1-1,len2-1);
    if(c)
      printf("Data set %d: yes\n",t);
    else
      printf("Data set %d: no\n",t);        
  }  
  return 0;    
}

• Re:DP记忆化就OK了。OMS (11) zpdlut 2010-09-08 10:30:40