动态规划经典题目（三）：最长公共子序列（LCS）

写最长上升子序列和最长公共子序列两篇博客都是为了后面的最长公共上升子序列准备啊~

一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则它就是这两个序列的最长公共子序列（Longest Common Sequence，简称LCS）。

一般求LCS，我们都采用动态规划解决。求两个序列的LCS一看找不到入手点，不像tower那题一样有明显的走向，所以难以推出上一步，难以划分子问题。仔细想想，存在公共子序列，就存在两个序列中存在元素相等（即A[i]=B[j]）的情况。那么我们就会想到枚举i和j。

（分析中所说的序列均为数组，下标从1开始，并非字符串）假设两个序列分别为A（长度为n）、B（长度为m），定义：F[i][j]表示 A的第i位及之前 这段子序列与 B的第j位及之前 这段子序列，这两段子序列的LCS长度。分析一下：如果A[i]=B[j]，那么F[i][j]就是F[i-1][j-1]+1，也就是说公共子序列加了一位（这位上是「公共的」）；如果A[i]≠B[j]，那么F[i][j]就是F[i-1][j]和F[i][j-1]里最大的（因为A[i]或者B[j]加不加都和答案没关系）。那么很容易得到转移方程：

F[i][j]=max(F[i-1][j-1]+(A[i]==B[j]),F[i-1][j],F[i][j-1]);

最长公共子序列(lcs.pas/c/cpp)

• 问题描述

给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X、Y的公共子序列。例如，若X=<A,B,C,B,D,A,B>，Y=<B,D,C,A,B,A>，那么<B,C,A>是X和Y的一个公共子序列，<B,C,B,A>也是X和Y的一个公共子序列。

编程求出给定的两个序列中，最长公共子序列的长度。

• 输入格式

• 输出格式

• 输入样例

aabaaecd
abcd

• 输出样例

4
abcd

• 代码

不见了！
（懒得写代码了，有时间再补吧zzz）