基准时间限制：1 秒 空间限制：131072 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
利用递归来实现对字符串的输出，在输入字符串a，b之后利用状态转移方程进行处理，再用一个数组进行该状态的标记，最后在递归函数里来进行操作
// 状态转移方程：
// if( s[i]==t[j] )
// dp[i+1][j+1] = dp[i][j] + 1;
// else
// dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
char a[maxn], b[maxn], k[maxn];
int dp[maxn][maxn];
int stal[maxn][maxn];//标记两个位置的字母是否相同，相同为0，不同为1
void Print(int i, int j)
{
if( i==0 || j==0 ) return ;
if( !stal[i][j] )//如果a[i]和b[j]子母相同，输出
{
Print(i-1, j-1);
printf("%c", a[i-1]);
}
else if( stal[i][j]==1 )//如果dp[i-1][j]>dp[i][j-1]
Print(i-1, j);
else//如果dp[i][j-1]>=dp[i-1][j]
Print(i, j-1);
}
int main()
{
gets(a);
gets(b);
int len1 = strlen(a), len2 = strlen(b);
// 用stal数组对a,b数组的元素和状态转移方程进行标记
for( int i=1; i<=len1; i++ )
{
for( int j=1; j<=len2; j++ )
{
if( a[i-1]==b[j-1] )
{
dp[i][j] = dp[i-1][j-1] + 1;
stal[i][j] = 0;
}
else
{
if( dp[i-1][j]>dp[i][j-1] )
{
dp[i][j] = dp[i-1][j];
stal[i][j] = 1;
}
else
{
dp[i][j] = dp[i][j-1];
stal[i][j] = -1;
}
}
}
}
Print(len1, len2);
return 0;
}