一、 介绍
LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。
例如：X=<A,B,C,E,A,C>和Y=<B,F,C,A,C,D>两个序列的最长公共子序列为Z=<B,C,A>
二、 动态规划算法思想
1) 最优子结构
---------------------图来自《算法导论P209页》
其实动态规划算法的思想最重要的一步也就是这一步，简单来说就是要找到构成最优解的一个子结构。假如这个子结构满足最优性，则可以采用动态规划自底向上来求解整体最优解。
本题中，我们假设序列X=<x1,x2,x3,x4……xm>和Y=<y1,y2,y3……yn>是需要求解最长公共子序列的两个串。我们假设X和Y存在一个最长公共子序列Z=<z1,z2,z3….zk>。
则Z和X、Y序列满足下列的关系式：
假如xm=yn，则我们可以取zk=xm，zk-1是xm-1和yn-1的最长公共子序列。假如X和Y存在某个最长公共子序列，且xm=yn，那么我们可以知道，至少xm或者yn两者之一是存在这个最长公共子序列中，否则两个都不存在的话，我们只要将xm和yn拼接上去，就得到一个更长的公共子序列，与假设不成立。假如只有xm在公共子序列中，而yn不在公共子序列中的时候，我们可以yn替换成Y的最后一个字符。同理如果xm不在公共子序列中，我们可以把xm和最后一位替换一下。那么可以保证取zk=xm都可以得到一个最长公共子序列。
如上图中，假如某个最长公共子序列的X是到k终止，Y序列是到n终止（不可能最长子序列X在m之前且Y序列在n之前，容易理解）。在这个情况下，我们只要将k直接移动到m上，即取m中的A为X序列中的最后一个字符即可。
假如xm≠yn，那么zk则需要从Xm-1和Yn或者Xm和Yn-1的最长公共子序列中取最大值。
2) 递归解
根据上述说明，可以得到下述递归解。其中c[i,j]表示序列Xi和Yj的最长公共子序列的长度。
---------------------图来自《算法导论P210页》
3) 自底向上求解
具体代码如下：
#include <iostream>
#include <stack>
using namespace std;
//预定义
#define m 7
#define n 6
//最长公共子序列函数
void LCS(char* x,char* y)
{
//输出序列
int out[n]={0};
//要生成的矩阵
int c[m+1][n+1];
char b[m+1][n+1];
//初始化
for(int i=0;i<=m;i++)
{
c[i][0]=0;
b[i][0]='-';
}
for(int j=0;j<=n;j++)
{
c[0][j]=0;
b[0][j]='|';
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(x[i]==y[j])
{
//若两个元素相等，则加1
c[i+1][j+1]=c[i][j]+1;
b[i+1][j+1]='\\';
}
else
{
//若不相等，从最大值中传递
if(c[i][j+1]>=c[i+1][j])
{
c[i+1][j+1]=c[i][j+1];
b[i+1][j+1]='|';
}
else
{
c[i+1][j+1]=c[i+1][j];
b[i+1][j+1]='-';
}
}
}
}
//输出矩阵
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{
cout<<c[i][j]<<" ";
}
cout<<endl;
}
//输出方向标
cout<<endl;
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{
cout<<b[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
//最长公共子序列进栈
i=m;j=n;
stack<char> myStack;
while(i>0 && j>0)
{
if(b[i][j]=='\\')
{
myStack.push(x[i-1]);
}
if(b[i][j]=='|')
i--;
else
j--;
}
//出栈输出
cout<<"最长公共子序列为：";
while(!myStack.empty())
{
cout<<myStack.top();
myStack.pop();
}
cout<<endl;
}
int main()
{
//调用函数
LCS("ABCBDAB","BDCABA");
return 0;
}
4) 由解信息构造出最优解
输入如图：
输出结果和教材给出的示例图相同。为了方便实现，本算法没有动态构造二维数组，而是直接定义好了两个字符串的长度，直接作为已知参数来构造二维数组，这里也是为了更方便说明算法，而不想把时间花在C语言或者C++语言的具体细节上，最后构造最优解，书中是采用了递归的方法，这里直接在一个函数里，因此直接采用数据结构栈来实现相同的功能。
教材例图：
---------------------图来自《算法导论P211页》
帖子来自IT部落格(http://www.itbuluoge.com)