一、什么是最长公共子序列？
公共子序列：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。（子序列Y中的字符在X中不一定是连续的。
最长公共子序列：找到的所有子序列中，字符最长的序列。
二、如何求解？
方法一：穷举法：列出X的所有子序列，一一检查是否是Y的子序列，记录所发现的公共子序列，最终求出最长公共子序列
无疑，方法一是很费时费力的；
方法二：刻画最长公共子序列问题的最优子结构
求解：
引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i]= Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。
问题的递归式写成：
这个递归式可以解释为：
1、当比较不开始时，两个序列没有公共序列；
2、当两个序列比较时，比较的两个字符相同，公共序列的长度为前一个已经计算出的公共序列的长度+1；
3、当两个序列比较时，比较的两个字符不同，公共序列的长度有两个，分别是两个序列在前一个状态下所求出的公共序列的长度，要这两个公共序列中最长的一个。
注意，这里c[i][j]是公共序列的长度，不是具体的公共序列，以二维数组的方式存储，i和j可以看做是在坐标系中的横纵坐标。
Java代码如下：
Public class LCSProblem { /** *初始化 **/ publicstaticvoidmain(String[]args) { String[]x={"","A","B","C","B","D","A","B"}; //初始化序列X； String[]y={"","B","D","C","A","B","A"}; //初始化序列Y； int[][]b=getLength(x,y); //将两个序列的最长公共序列的长度值记录在二维数组b中； Display(b,x,x.length-1,y.length-1); //输出； /** *计算最长公共子序列的长度 **/ Public static int[][]getLength(String[]x,String[]y) { int[][]b=new int[x.length][y.length]; //初始化数组b，记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。 int[][]c=new int[x.length][y.length]; //初始化数组c，记录X[i]与Y[j] 的LCS 的长度。 //填充矩阵 for(int i=1;i<x.length;i++) { for(int j=1;j<y.length;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; //1代表指向左上方的箭头 } elseif(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=0; //0代表指向上方的箭头 } else { c[i][j]=c[i][j-1]; b[i][j]=-1; //-1代表指向左方的箭头 } } } Return b; }
用箭头的指向，表示序列中有公共的值时，该解是在求解哪个子问题的基础上得来。
/** *输出最长公共子序列 **/ void PrintLCS(int b[][], char x, int i, int j) { if(i == 0 || j == 0) //两个字符串中任意一个长度为0； return null; if(b[i][j] == 1) //箭头指向左上方 { PrintLCS(b, x, i-1, j-1); printf("%c ", x[i-1]); //输出两个序列相同的字符 } else if(b[i][j] == 0) //箭头指向上方 PrintLCS(b, x, i-1, j); else //箭头指向左方 PrintLCS(b, x, i, j-1); }
三、复杂度：
时间复杂度：构建矩阵我们花费了O(MN)的时间，回溯时我们花费了O（M+N)的时间，两者相加最终我们花费了O(MN)的时间。
空间复杂度：构建矩阵我们花费了O(MN)的空间，标记函数也花费了O(MN)的空间，两者相加最终我们花费了O(MN)的空间。
四、应用：
查重，相似度分析，查找最长递增子序列等；
这些应用，你有没有想到呢？
参考资料：
http://blog.csdn.net/yysdsyl/article/details/4226630/
http://blog.sina.com.cn/s/blog_54f82cc20100zi4b.html
http://blog.csdn.net/amazingcode/article/details/51694332
