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

一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则它就是这两个序列的最长公共子序列（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]);

显然最后的答案就是F[n][m]。时间复杂度是O（N²）。再开个二维数组s记录答案就可以了。以下是原题……

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

• 问题描述

一个给定的子序列是在该序列中删去若干元素后得到的序列。例如，序列Z=是序列X=的子序列。

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

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

• 输入格式

共两行，各一个字符串，第一个字符串表示第一个序列，第二个字符串表示第二个序列，两个字符串，长度均小于1000。

• 输出格式

第一行：一个整数，即两个序列的公共子序列的长度。
第二行：最长公共子序列，如有多解，则尽量以第一个字符串为主。

• 输入样例

aabaaecd

abcd

• 输出样例

4abcd

• 代码

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