算法基础四：动态规划---最长公共子序列

一、算法描述与分析

1、问题的理解与描述

• 子序列：
  • 已知序列的子序列是在已知序列中去掉零个或多个元素后形成的序列。例如，Z=<B,C,D,B>是X=<A,B,C,B,D,A,B>的一个子序列。
• 公共子序列：
  • 给定两个序列X和Y，若Z同时为X和Y的子序列，我们说序列Z是X和Y的一个公共子序列。X和Y的公共子序列中长度最大者，称为X和Y的最长公共子序列（Common Longest Subsequence，简记为LCS）。

问题描述：

• 输入：序列X=<x1,x2,.....,xm>和Y=<y1,y2,...yn>
• 输出：X与Y的一个最长公共子序列Z。

2、最长公共子序列的最优子结构

递归式：

3、图解

①初始化

②相等的情况

③不等的情况

④转移方程

if (a == b){
    table[row][col] = table[row - 1][col-1] + 1;
}else{
    table[row][col]=Math.max(table[row][col-1],table[row-1][col]);
}

二、算法的伪代码描述

1、伪代码

LCS-LENGTH (X,Y)
	m <- length[X]
	n <- length[Y]
	for i <- 1 to m
		do c[i,0] <- 0
    for j <- 0 to n
    	do c[0,j] <- 0 
    for i <- 1 to m 
    	do for j <- 1 to n
    		do if xi = yj
    			then c[i,j] <- c[i-1,j-1] + 1
    			else if c[i-1,j] >= c[i,j-1]
    				then c[i,j] <- c[i-1,j]
    				else c[i,j] <- c[i,j-1]
   	return C

2、构造一个最优解

我们可以用如下的过程来根据表格c构造出最优解

PRINT-LCS(c,X,Y,i,j)
	if i = 0 or j = 0
		then return
	if xi = yi
		then PRINT-LCS (c,X,Y,i-1,j-1)
			print xi
		elseif c[i-1,j] >= c[i,j-1]
			then PRINT-LCS (c,X,Y,i-1,j)
			else PRINT-LCS (c,X,Y,i,j-1)

三、程序实现

1、算法代码

​ 使用Object顶级类来作为序列x和y的元素类型。Object对象本身就有检测相互是否相等的方法equals。

public class Lcs {
    public static int[][] lcsLength(Object[] x,Object[] y) {
        int m = x.length, n = y.length, i, j;
        int[][] c = new int[m + 1][n + 1];
        for (i = 1; i <= m; i++)
            c[i][0] = 0;
        for (j = 0; j <= n; j++)
            c[0][j] = 0;
        for (i = 1; i <= m; i++)
            for (j = 1; j <= n; j++)
                if (x[i - 1].equals(y[j - 1]))
                    c[i][j] = c[i - 1][j - 1] + 1;
                else if (c[i - 1][j] >= c[i][j - 1])
                    c[i][j] = c[i - 1][j];
                else
                    c[i][j] = c[i][j - 1];
        return c;
    }

    public static void printLcs(int[][] c,Object[] x,Object[] y,int i,int j){
        if (i==0 || j==0)
            return;
        if (x[i-1].equals(y[j-1])){
            printLcs(c,x,y,i-1,j-1);
            System.out.print(x[i-1]+" ");
        }else if (c[i-1][j]>=c[i][j-1])
            printLcs(c,x,y,i-1,j);
            else
                printLcs(c,x,y,i,j-1);

    }

}

2、测试代码

public class Test {
    public static void main(String[] args) {
        Character[] x = {'A','B','C','D','A','B'},
                    y = {'B','D','C','A','B','A'};
        Integer[] a = {389,207,155,300,299,170,158,65},
                  b = {389,300,299,207,170,158,155,65};

        int [][]  c;
        c = Lcs.lcsLength(x,y);
        Lcs.printLcs(c,x,y,6,6);
        System.out.println();
        c = Lcs.lcsLength(a,b);
        Lcs.printLcs(c,a,b,8,8);
        System.out.println();
    }
}