hdu1501 (dp)

1         for(i=1;i<=lena;i++)
2             if(a[i]==c[i])  dp[i][0]=1;//在第0行和第0列，如果有匹配到c字符串中的字符便把dp[0][i]或dp[i][0]置为1，否则为0.这就算dp的初始值。
3             else dp[i][0]=0;
4         for(i=1;i<=lenb;i++)
5             if(b[i]==c[i])  dp[0][i]=1;
6             else dp[0][i]=0;

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 char a[205],b[205],c[405];
 5 int dp[205][205];
 6 int main()
 7 {
 8     int T;
 9     scanf ("%d",&T);
10     for(int t=1;t<=T;t++)
11     {
12         a[0]=b[0]=c[0]=‘0‘;
13         scanf ("%s %s %s",a+1,b+1,c+1);//我们刻意让字符串的起始地址为1
14         int lena=strlen(a)-1;
15         int lenb=strlen(b)-1;
16         int i,j,k;
17         for(i=1;i<=lena;i++)
18             if(a[i]==c[i])  dp[i][0]=1;
19             else dp[i][0]=0;
20         for(i=1;i<=lenb;i++)
21             if(b[i]==c[i])  dp[0][i]=1;
22             else dp[0][i]=0;
23         for(i=1;i<=lena;i++)
24         {
25             for(j=1;j<=lenb;j++)
26             {
27                 dp[i][j]=((dp[i-1][j]&&a[i]==c[i+j])||(dp[i][j-1]&&b[j]==c[i+j]));//递推求dp的值
28             }
29         }
30         /*for(i=0;i<=lena;i++)
31         {
32             for(j=0;j<=lenb;j++)
33                 printf("%d ",dp[i][j]);
34             printf("\n");
35         }*/
36         printf("Data set %d: ",t);
37         if(dp[lena][lenb])
38             printf("yes\n");
39         else
40             printf("no\n");
41     }
42     return 0;
43 }

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 char a[205],b[205],c[405];
 5 int la,lb,lc,flag;
 6 int visit[205][205];
 7 void dfs(int i,int j,int k)
 8 {
 9     if(k==lc)//当然，如果搜索到k等于c的长度的话，那么肯定是yes了
10     {
11         flag=1;
12         return ;
13     }
14     if(visit[i][j])//为什么要加visit数组，我觉得是记忆化搜索。
15         return ;
16     visit[i][j]=1;
17 
18     if(a[i]!=c[k]&&b[j]!=c[k])//如果c的k这个位置a和b都不符合。那么就return。
19         return ;
20     if(a[i]==c[k]&&i+1<=la)//如果a[i]==c[k]而且i+1小于a的长度la的话，进入下一个字符。
21         dfs(i+1,j,k+1);
22     if(b[j]==c[k]&&j+1<=lb)//同理
23         dfs(i,j+1,k+1);
24 }
25 int main()
26 {
27     int T;
28     scanf ("%d",&T);
29     for(int t=1;t<=T;t++)
30     {
31         scanf ("%s %s %s",a,b,c);
32         la=strlen(a);
33         lb=strlen(b);
34         lc=strlen(c);
35         flag=0;
36         memset(visit,0,sizeof(visit));//对visit初始化
37         dfs(0,0,0);
38         if(flag)
39             printf("Data set %d: yes\n",t);
40         else
41             printf("Data set %d: no\n",t);
42     }
43     return 0;
44 }