我们称Z=<z1,z2,z3,z4....zn>是序列X=<x1,x2,x3,x4..xm>的子序列当且仅当存在严格上升的序列<i1,i2,i3,i4...in>使得j=1,2,3,...k，有Xij=Zj。

设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共子序列记为LCS(X,Y)

找出LCS(X,Y)就是一个最优化问题。因为，我们需要找到X 和 Y中最长的那个公共子序列。而要找X 和 Y的LCS，首先考虑X的最后一个元素和Y的最后一个元素。

 1）如果 xn=ym，即X的最后一个元素与Y的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS(Xn-1，Ym-1)

2）如果xn != ym，这下要麻烦一点，因为它产生了两个子问题：LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)

因为序列X 和 序列Y 的最后一个元素不相等，那说明最后一个元素不可能是最长公共子序列中的元素。（不相等了，不可能公共）。

LCS(Xn-1，Ym)表示：最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找。

LCS(Xn，Ym-1)表示：最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找。

这里的解释更好理解（翻到一位dalao的）

点这里

最长公共子序列的递推式：

例题：

输入包括多组数据，每组数据给出两个不超过200的字符串表示两个序列，两个字符串之间由若干个字符串分开。

输入样例：

abcfbc     abfcab

asd     kjl

count       aont

输出样例

4

0 

3

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream> 
using namespace std;#define max1 1000char str1[max1];//定义两个字符串 
char str2[max1];int dp[max1][max1];//这里的dp二维组就是最长公共子序列相当于maxlen[max1][max1];int main()
{while(scanf("%s%s",str1+1,str2+1)>0)//+1字符串地址从1开始，而不是0 {int len1 = strlen(str1+1); int len2 = strlen(str2+1);int tmp;for(int i=0; i<=len1; i++)//初始化dp数组，字符串均不为空，地址从1开始 dp[i][0]=0;for(int i=0; i<=len2; i++)dp[0][i]=0;for(int i=1; i<=len1; i++)//动态规划核心{for(int j=1; j<=len2; j++){if(str1[i] == str2[j])dp[i][j] = dp[i-1][j-1]+1;else{dp[i][j]= max(dp[i-1][j],dp[i][j-1]);}}}printf("%d\n",dp[len1][len2]);//输出最长公共子序列 }return 0;
}

 路径：

#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
using namespace std;
#define N 1010
int dp[N][N];
char c;
int main()
{char a[N];char b[N];scanf("%s%s",a,b);int la=strlen(a);int lb=strlen(b);memset(dp,0,sizeof(dp));for(int i=1; i<=la; i++){for(int j=1; j<=lb; j++){if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}int i=la,j=lb;stack<char>s;while(dp[i][j]){if(dp[i][j]==dp[i-1][j])///来自于左方向{i--;}else if(dp[i][j]==dp[i][j-1])///来自于上方向{j--;}else if(dp[i][j]>dp[i-1][j-1])///来自于左上方向{i--;j--;s.push(a[i]);}}while(!s.empty()){c=s.top();printf("%c",c);s.pop();}return 0;
}