动态规划思想：把一个大的问题分解成若干个子问题，求出子问题后，然后回溯求出大的问题。
分析：给定两个字符串，假设为“a0,a1,a2....an”和"b0,b1,b2...bm",要求出两个字符串的最长公共子序列，我们先把大问题分成小问题，举个例子吧！
假设“c0,c1,c2...ck”为它们的最长公共子序列。第一种：an=bm,则“c0,c1,c2...c(k-1)”为“a0,a1,a2...a(n-1)”和"b0,b1,b2...b(m-1)"的最长公共子序列；
第二种：an!=bm并且an!=ck则“c0,c1,c2...ck”为"a0,a1,a2....a(n-1)"和"b0,b1,b2...bm"的最长公共子序列；第三种：an!=bm并且bm!=ck，
则“c0,c1,c2...ck”为"a0,a1,a2....an"和"b0,b1,b2...b(m-1)"的最长公共子序列.
求解：
引进一个二维数组dp[][]，用dp[i][j]记录a[i]与b[j] 的LCS 的长度，flag[i][j]记录dp[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算dp[i,j]之前，dp[i-1][j-1]，dp[i-1][j]与dp[i][j-1]均已计算出来。此时我们根据a[i] = b[j]还是a[i] != b[j]，就可以计算出dp[i][j]。
问题的递归式写成：
回溯输出最长公共子序列过程：
算法分析：
由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m * n)。
代码实现：
#include<stdio.h>
#include<string.h>
char a[1000],b[1000];
int dp[1000][1000],flag[1000][1000],len1,len2,i,j;
int lsc()//求最长公共子序列的长度并且记录路劲
{
for(i=0;i<=len1;i++)
dp[i][0]=0;
for(j=0;j<=len2;j++)
dp[0][j]=0;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(a[i-1]==b[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
flag[i][j]=0;
}
else
{
if(dp[i-1][j]>=dp[i][j-1])
{
dp[i][j]=dp[i-1][j];
flag[i][j]=1;
}
else
{
dp[i][j]=dp[i][j-1];
flag[i][j]=2;
}
}
}
return dp[len1][len2];
}
void printflsc(int x,int y)//回溯输出最长公共子序列
{
if(x==0||y==0)
return;
if(flag[x][y]==0)
{
printflsc(x-1,y-1);
printf("%c ",a[x-1]);
}
else if(flag[x][y]==1)
printflsc(x-1,y);
else
printflsc(x,y-1);
}
int main()
{
int t;
while(scanf("%s%s",a,b)!=EOF)
{
len1=strlen(a);
len2=strlen(b);
t=lsc();
printf("%d\n",t);
if(t)
{
printflsc(len1,len2);
printf("\n");
}
}
return 0;
}