题意：
给你两个字符串，求一个最短的串，使得输入的两个串均是他的子序列（不一定连续）
思路：
可以看出ans = 两个串的长度和 - 两个串的最长公共子序列，在最后的构造处GG。
在构造时想了很久，想复杂了- -，后来看别人思路完全可以根据最长公告子序列的原理来
而且下次可以考虑画个图来看
①a[i] == b[j]说明ans[i][j]只需要在ans[i-1][j-1]的组合基础上加一个字母a[i](b[j]),所以ans[i][j] = ans[i-1][j-1]
②不相等时
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
1.假设dp[i][j-1] > dp[i-1][j]
说明ans[i][j]需要在ans[i][j-1]的组合基础上加一个字母b[j],所以ans[i][j] = ans[i][j-1]
2.dp[i-1][j] > dp[i][j-1] 的原理同上
3.如果dp[i][j-1] == dp[i-1][j]，则说明我们两种都选，ans[i][j-1]的组合基础上加一个字母b[j]
或者 ans[i-1][j]的组合基础上加一个字母a[i],所以ans[i][j] = ans[i][j-1] + ans[i-1][j];
感觉对动归的理解不到位- -，Wo好弱
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn= 50;
char a[maxn];
char b[maxn];
int dp[maxn][maxn];
ll tans[maxn][maxn]; int main()
{
int n;
scanf("%d",&n);
getchar();
int cas = 1;
while(n--)
{ gets(a+1);
gets(b+1);
int lena = strlen(a+1);
int lenb = strlen(b+1);
memset(dp,0,sizeof(dp));
for(int i = 0; i <= lena; i++)
tans[i][0] = 1;
for(int j =0; j <= lenb; j++)
tans[0][j] = 1;
for(int i = 1; i <= lena; i++)
for(int j = 1; j <= lenb; j++)
{
if(a[i] == b[j]) //相等则只需在后面加上字母
{
dp[i][j] = dp[i-1][j-1] + 1;
tans[i][j] = tans[i-1][j-1];
}
else if(dp[i][j-1] > dp[i-1][j])
{
dp[i][j] =dp[i][j-1];
tans[i][j] = tans[i][j-1];
}
else if(dp[i-1][j] > dp[i][j-1])
{
dp[i][j] =dp[i-1][j];
tans[i][j] = tans[i-1][j];
}
else
{
dp[i][j] =dp[i][j-1];
tans[i][j] = tans[i][j-1] + tans[i-1][j];
}
}
int ans =lena+lenb-dp[lena][lenb];
printf("Case #%d: %d %lld\n",cas++,ans,tans[lena][lenb]);
}
return 0;
}