hdu1501-poj2192详细解题报告

第一眼看到这个题目就想到用字符串模拟....自己嫩得跟什么似得.....后面问了学长...自己想了很久，然后这里给出详细结题报告：个人觉得这个对于刚接触 dp 的人来说是一个比较好的经典题目，很有dp的思维(对于目前菜菜的我来说)

题意：给你三个字符串，A、B、C，问你A和B能否组成C，当然是有要求的，那就是所有组成C的字母一定要按照A和B的顺序来，不能乱，意思就是从C中按顺序把组成A(或B)的所有字母拿出来，剩下的就是B(或A)

分析：首先给出详细分析如何得到dp状态转移方程，然后就是详细的实现过程(很多地方结合图形有利于理解分析)

首先，我们可以知道 C 的最后一个字母，要不是由 A的最后一个组成，要不就是B的最后一个组成，那么对于C的任意一位(这里说成)第 i + j 位要么就是由A的 i 位 或者 B 的 j 位组成，那么这个先给出 一个数组 dp[i][j] (它的行是由A的所有字母按顺序组成，列是B组成，比如题目的案例可以有以下图:

),它的值为 1 的时候表示 C 的 第 i + j 位 可以由A 的i 或者 B 的j 组成，为0 则表示不可以，那么我们对于整个的是否可以组成C我们可以用两个循环列举去组成的所有情况：for循环如下

那么为什么要这样搭配出状态转移呢？
可以用下面的图理解：
由图可以知道，我们反过来就是得到dp[i][j]的思路
那么分析到这里，还有一个地方要注意，我们对于给出的那么dp[i][j]的二维数组前面的i=0的那一行和j=0的那一列空出来了，那就是要做边界处理的情况，我们要枚举每一种组成情况组成那么当然就有 c[i][j] i=0时 只有B的j组成c的情况。。。。
上马：
#include<stdio.h>#include<string.h>#define MAX 201int dp[MAX][MAX];char A[MAX],B[MAX],C[MAX*2];int main(){int T;int i,j;scanf("%d",&T);A[0]=B[0]=C[0]='0';for(int cas=1;cas<=T;cas++){scanf("%s%s%s",A+1,B+1,C+1);//这里都从下标为1开始int a=strlen(A)-1,b=strlen(B)-1;for(i=1;i<=a;i++)//边界处理if(A[i]==C[i])dp[i][0]=1;else            dp[i][0]=0;for(i=1;i<=b;i++)//边界处理if(B[i]==C[i])dp[0][i]=1;else            dp[0][i]=0;for(i=1;i<=a;i++)for(j=1;j<=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: ",cas);if(dp[a][b])printf("yes\n");elseprintf("no\n");}return 0;}
个人愚昧观点，欢迎指正与讨论