题目描述
一天小明和小红在玩单词混合的游戏，游戏的规则是按顺序给出3个单词，判断第3个单词是否能够由前两个单词中的所有字母混合而成。
前两个单词可以任意混合，但是混合后，原本两个单词中的字符前后顺序必须与原单词中的顺序保持一致。
输入格式
输入的第一行为一个正整数n（1<=n<=1000），表示测试样例的个数。
接下来n行，每行输入输入3个字符串，字符串之间由一个空格分隔，所有的字符串仅由英文大小写字母组成，区分大小写，即'A' != 'a'。
输入数据保证第3个字符串的长度是前两个字符串长度之和，前两个字符串的长度范围是[1,200]。
输出
对于每个输入样例，首先输出“Case N: ”，N表示样例序号，从1开始。
如果第3个单词能够按照要求由前两个单词中的所有字母混合而成，则紧接着输出“yes”，否则输出“no”。
样例输入
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
样例输出
Case 1: yes
Case 2: yes
Case 3: no
这题是一道字符串dp的题，一般字符串dp都要设为二维的,dp[i][j],i,j分别指向两个字符串。然后建立动态规划方程。我找了很久，还是没有什么头绪，可能是字符串的dp题做得太少了，以前也只有做过编辑距离的题呀。
dp[i][j]表示A串的前i个字符，B串的前j个字符能够组成C串的i+j个字符。
dp[i][j]=1 当且仅当(dp[i-1][j]==1&&a[i-1]==c[i+j-1])或者(dp[i][j-1]==1&&b[j-1]==c[i+j-1])
代码：
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 2005
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
char a[202],b[202],c[202];
bool dp[202][202];
int main()
{
int n;
cin>>n;
for(int t=1;t<=n;t++)
{
cin>>a>>b>>c;
//初始化dp[i][j],A串前i个字符，B串前j个字符能否构成C串前i+j个字符
memset(dp,0,sizeof(dp));
for(int i=1;i<=strlen(a);i++)
{
if(a[i-1]==c[i-1])
dp[i][0]=1;
else
break;
}
for(int i=1;i<=strlen(b);i++)
{
if(b[i-1]==c[i-1])
dp[0][i]=1;
else
break;
}
for(int i=1;i<=strlen(a);i++)
{
for(int j=1;j<=strlen(b);j++)
{
if((dp[i][j-1]==1&&b[j-1]==c[i+j-1])||(dp[i-1][j]==1&&a[i-1]==c[i+j-1]))
dp[i][j]=1;
else
dp[i][j]=0;
}
}
printf("Case %d: ",t);
if(dp[strlen(a)][strlen(b)])
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return 0;
}