Description
给定3个字符串a, b, c。你的任务是判断c是否可由a, b拼接出来。
c可由a, b拼接则意味着存在一种情况，将c拆分成两个子字符串，这两个子字符串分为等于a, b。注，c在拆分过程中，c中的每个字符只能属于两个子串中的一个。
Input
输入包含多组样例，样例数不超过20。
第一行一个整数T，表示样例数。
接下来3T行，每三行为一组样例。每组样例包含3行，分别为字符串a, b, c（1≤字符串长度≤2×103）。
Output
对于每组输入，输出Yes，如果c可由a, b拼接; No，如果不可拼接。
样例输入
2
abc
def
adebcf
abc
def
abecdf样例输出
Yes
NoNote: 请注意，字符之间的顺序不能改变。
1.确定状态：dp[i][j]:表示第 1 个字符串的第 i 个字符，第 2 个字符串的第 j 个位置
2.状态转移：dp[i][j]=dp[i][j]||dp[i-1][j];
dp[i][j]=dp[i][j]||dp[i][j-1];
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=2e3+7;
string a,b,c;
int dp[maxn][maxn];
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0);
int t;
cin>>t;
while(t--){
memset(dp,0,sizeof dp);
cin>>a>>b>>c;
int la=a.size(),lb=b.size(),lc=c.size();
if(la+lb==lc){
dp[0][0]=1;
for(int i=0;i<=la;++i){
for(int j=0;j<=lb;++j){
if(!i && !j) continue;
if(i){
if(a[i-1] == c[i+j- 1])
dp[i][j]=dp[i][j]||dp[i-1][j];
}
if(j){
if(b[j-1]==c[i+j-1])
dp[i][j]=dp[i][j]||dp[i][j-1];
}
}
}
if(dp[la][lb]) cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
else cout<<"No"<<'\n';
}
return 0;
}