时间限制：1 秒 空间限制：65536 KB 分值: 0 给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。 比如两个串为： abcicba abdkscab ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。 Input 第1行：字符串A 第2行：字符串B (A,B的长度 <= 1000) Output 输出最长的子序列，如果有多个，随意输出1个。 Input 示例 abcicba abdkscab Output 示例 abca
动态规划的一个计算两个序列的最长公共子序列的方法如下：
以两个序列 X、Y 为例子：
设有二维
数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：
f[1][1] = same(1,1);
f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}
其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”，否则为“0”。
此时，二维数组中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该
数组回溯，便可找出最长公共子序列。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str1[1002],str2[1002];
int d[1002][1002];
int main()
{
while(gets(str1) && gets(str2))
{
int len1=strlen(str1),len2=strlen(str2);
memset(d,0,sizeof(d));
for(int i=len1-1; i>=0; i--)
for(int j=len2-1; j>=0; j--)
{
if(str1[i]==str2[j])
d[i][j]=d[i+1][j+1]+1;
else
d[i][j]=max(d[i+1][j],d[i][j+1]);
}
int i = 0, j = 0;
while (i < len1 && j < len2){
if (str1[i] == str2[j]){
printf("%c",str1[i]);
i++;
j++;
}
else if (d[i+1][j] >= d[i][j+1])
i++;
else
j++;
}
printf("\n");
}
return 0;
}
