《算法设计与分析》--最长公共子序列随笔

1.定义

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}。

给定两个序列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的一个公共子序列，但是它不是X和Y的最长公共子序列。序列{B,C,B,A}也是X和Y的一个公共子序列，它的长度是4，而且它是X和Y的最长公共子序列，因为X和Y没有长度大于4的公共子序列。

2.解决方法

动态规划可以有效的解决此问题。事实上最长公共子序列问题具体最优子结构的性质。

3.性质

两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因为最长公共子序列问题具有最优子结构的性质，因此是可以使用动态规划算法解决的。

事实上，设序列X={x1,x2,...,xm}和Y={y1,y2,y3,...yn}的最长公共子序列为Z={z1,z2,z3,...,zk}

那么我们可以的出来

(1)如果xm = yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列;

(2)如果xm!=yn,且zk!=xm,则Z是xm-1和Y的最长公共子序列。

(3)如果xm!=yn,且zk!=yn,则z是X和Yn-1的最长公共子序列。

4.计算最优质值

计算最长公共子序列长度的动态规划算法以序列X={x1,x2,x3,..,xn}和Y={y1,y2,y3,...yn}作为输入。输出两个数组c和b。其中c[i][j]存储的是xi和yj的最长的公共子序列的长度，b[i][j]记录的值是由哪一个子问题的一些解得到的，这个算法的最优值记录与c[m][n]当中。

代码段:

public static int lcsLength(char[] x,char[] y,int [][]b){


int m = x.length-1;
int n = y.length-1;
int[][]c = new int[m+1][n+1];
for(int  i =1;i<=m;i++)c[i][0] = 0;
for(int  i =1;i<=n;i++)c[0][i] = 0;
for(int i = 11;i<=m;i++)
for(int j = 1;j<=n;j++){
if(x[i] == y[j]){
c[i][j] = c[i-1][j-1]+1;
b[i][j] = 1;
}
else if(c[i-1][j]>=c[i][j-1]){
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
return c[m][n];
}