題意：給你3個(gè)字符串，問(wèn)你在不改變前2個(gè)字符串排列順序的情況下能否組成第三個(gè)字符串。
解法：DP，狀態(tài)設(shè)計(jì)，a[i][j]為1表示第一個(gè)字符串的前j個(gè)和第二個(gè)字符串的前i個(gè)可以組成第三個(gè)字符串的前i+j個(gè)，否則為0；
這樣轉(zhuǎn)移方程為：當(dāng)a[i-1][j]為1且s2[i]==s[i+j]或者a[i][j-1]為1且s1[j]==s[i+j]時(shí)a[i][j]為1。
#include <stdio.h>
#include <string.h>
#define N 405
char s1[N], s2[N], s[N];
bool a[N][N];
int main()
{
int t, l1, l2;
scanf("%d", &t);
for(int k = 1; k <= t; k++)
{
scanf("%s %s %s", &s1, &s2, &s);
memset(a, 0, sizeof(a));
l1 = strlen(s1), l2 = strlen(s2);
a[0][0] = 1;
for(int i = 0; i < l1; i++)
{
a[0][i + 1] = (a[0][i] && s1[i] == s[i]);
}
for(int i = 0; i < l2; i++)
{
a[i + 1][0] = (a[i][0] && s2[i] == s[i]);
}
for(int i = 1; i <= l2; i++)
{
for(int j = 1; j <= l1; j++)
{
if(a[i - 1][j] || a[i][j - 1])
{
if(a[i - 1][j] && s2[i - 1] == s[i + j - 1]) a[i][j] = 1;
if(a[i][j - 1] && s1[j - 1] == s[i + j - 1]) a[i][j] = 1;
}
}
}
printf("Data set %d: %s\n", k, a[l2][l1] ? "yes" : "no");
}
return 0;
}