动态规划之最长公共子序列
原文在这里 http://blog.csdn.net/dq_dm/article/details/45043689
1、LCS的基本概念
子序列：一个序列X任意删除若干个字符得到新序列Z，则Z叫做X的子序列。例如Z=是X=的子序列，相当于删除A、B、A。
公共子序列：给定两个序列X和Y，如果Z既是X的子序列，也是Y的子序列，我们称它为X和Y的公共子序列。公共子序列可能不唯一。例如是X=和Y=的一个公共子序列。
最长公共子序列：Longest Common Subsequence，简称LCS。如果Z是X和Y的公共子序列，且是最长的那个，则称Z是X和Y的最长公共子序列。例如是X=和Y=的一个最长公共子序列，也是。它也可能不唯一。
注：(1)为了简便，上面我们讨论的都是两个序列的公共子序列，当然，也可以是3个、4个等等。(2)它和最长公共子串是有区别的，最长公共子串要求连续。
求两个序列中最长的公共子序列算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、功能和演化过程。
LCS可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。
1）假定序列X，Y的长度分别为m，n；
2）X的一个子序列即下标序列{1, 2, …, m}的严格递增子序列，因此，X共有2m个不同子序列；同理，Y有2n个不同子序列，从而穷举搜索法需要指数时间O(2m .2n)；
3）对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列；
显然，不可取。
在这里先说些前缀的概念，给定一个序列X=，对i=0,1,…,m，定义X的第i前缀为Xi=。例如，若X=，则X4=，X0为空串。
令X=和Y=为两个序列，Z=为X和Y的任意LCS。
1）如果xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS。也就是
例如：
2）如果xm≠yn，那么zk≠xm意味着Z是xm-1和Y的一个LCS。
也就是，LCS(Xm,Yn)=LCS(Xm-1,Yn)。
3）如果xm≠yn，那么zk≠yn意味着Z是X和Yn-1的一个LCS。也就是，LCS(Xm,Yn)=LCS(Xm,Yn-1)。
例如：
显然，是动态规划问题。
引进一个二维数组c[0..m,0..n]，用c[i,j]记录序列Xi与Yj的LCS的长度。
引进一个二维数组b[1..m,1..n]，b[i,j]标记c[i,j]是由哪一个子问题的解求得的，以决定搜索的方向。即c[i,j]是由c[i-1,j-1]+1或者c[i-1,j]或者c[i,j-1]的哪一个得到的。取值范围为LeftTop、Top、Left三种情况。
举例：
X=< A，B，C，B，D，A，B >，Y=< B，D，C，A，B，A >
注：
1）第一行、第一列都为0；
2）按行主次序计算表项。
3）第i行和第j列的方格包含了c[i,j]的值和b[i-1,j]记录的箭头；
4）右下角的项c[7,6]中的4即为X和Y的一个LCS的长度；
5）为了构造LCS的元素，从右下角开始沿着b[i,j]的箭头前进即可，如图中阴影方格序列。阴影序列中每个“ ”对应的表项表示xi=yj是LCS的一个元素。此时得到的是BCBA，逆序输出，即LCS是。
过程的运行时间为O(mn)，因为每个表项的计算时间为O（1）。
开始的i、j分别是X和Y的长度。
过程的运行时间为O（m+n），因为每次递归调用i和j至少有一个会减少1。
java代码实现
public class algorithm {
public static void main(String[] args) {
char[] X = "BDCABA".toCharArray();
char[] Y = "ABCBDAB".toCharArray();
lcs(X, Y);
}
public static void lcs(char[] X,char[] Y){//求最长公共子序列长度
int m = X.length,n = Y.length;
int[][] c = new int[m + 1][n + 1];
int[][] b = new int[m + 1][n + 1];
for (int i = 0;i <= m;i++)
c[i][0] = 0;
for (int j = 0;j <= n;j++)
c[0][j] = 0;
for (int i = 1;i <= m;i++){
for (int j = 1;j <= n;j++){
if (X[i - 1] == Y[j - 1]){
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 7;
}else if (c[i - 1][j] >= c[i][j -1]){
c[i][j] = c[i - 1][j];
b[i][j] = 8;
}else{
c[i][j] = c[i][j - 1];
b[i][j] = 4;
}
}
}
System.out.println("最长公共子序列的长度为:" + c[m][n]);
System.out.println("其中的一个最长公共子序列为:");
lcs_list(b, X, m, n);
}
public static void lcs_list(int[][] b,char[] X,int m,int n){//求最长公共子序列
int i = m,j = n;
if (i == 0 || j == 0)
return ;
if (b[i][j] == 7){
lcs_list(b, X, i - 1, j - 1);
System.out.print(X[i - 1]);
}else if (b[i][j] == 8){
lcs_list(b, X, i - 1, j);
}else{
lcs_list(b, X, i, j - 1);
}
}
}
