动态规划-最长公共子序列

发表于： 分类于：
字数： 1081 阅读：≈ 3分钟 浏览：

算法思想：动态规划

实际问题：最长公共子序列

编写语言：Java

问题描述

子序列：是一个给定序列的子序列是在该序列中删去若干元素后得到的序列。如X={A, B, C, D}, {A, C}是X的子序列，{A, B, D}是X的子序列。

问题描述：给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列，X和Y的所有公共子序列中长度最长的即是X和Y的最长公共子序列。

值得一提的是，最长公共子序列不只一个，但构造的时候只能构造出一个。

关键特征

设序列X={x1, x2, x3, …, 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的最长公共子序列

其中：Xm-1={x1, x2, …, xm-1}，Yn-1={y1, y2, …, yn-1}，Zk-1={z1, z2, …, zk-1}。

递归结构

用c[i][j]记录序列Xi和Yj的最长公共子序列长度，那么：

  1. 当i=0, j=0时，c[i][j]=0
  2. 当i>0, j>0, xi=yj时，c[i][j] = c[i-1][j-1]+1
  3. 当i>0, j>0,xi!=yj时，c[i][j] = max{c[i][j-1], c[i-1][j]}

其中，第3点是说当xm!=yn时，求取Xm-1, Y和X, Yn-1两者的最长公共子序列的较长者作为整体的最长公共子序列

Java代码 

public class LongestCommonSubsequence
{
    public static void main(String[] args)
    {
        //第一个字符留空，可以省去后续很多麻烦
        char[] x = new char[]{' ', 'A', 'B', 'C', 'B', 'D', 'A', 'B'};
        char[] y = new char[]{' ', 'B', 'D', 'C', 'A', 'B', 'A'};
        
        int m = x.length;
        int n = y.length;
        
        int[][] c = new int[m][n];
        int[][] b = new int[m][n];
        lcsLength(m - 1, n - 1, x, y, c, b);
        lcs(m - 1, n - 1, x, b); //从m-1，n-1开始往下面找
        System.out.println();
    }
    
    /**
      * 参数含义：
      * m: X序列的长度
      * n: Y序列的长度
      * x, y: 待求最长公共子序列的原始序列
      * c: 记录Xi和Yj的最长公共子序列长度
      * b: 记录得到c[i][j]的是哪个子问题
    */
    public static void lcsLength(int m, int n, char[] x, char[] y, 
        int[][] c, int[][] b)
    {
        for(int i = 0; i < m; i++)
            c[i][0] = 0;
        for(int i = 0; i < n; i++)
            c[0][i] = 0;
        
        for(int i = 1; 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;
                }
            }
        }
    }
    
    /**
      * 该方法构造一个X，Y的最长公共子序列
      * 参数含义：
      * i, j: 序列X, Y的下标
      * x: 原始序列，因为构造的是X, Y的最长公共子序列。
      *     此处用Y也行，因为x有的y也有。
      *     但是序列应全程保持一致(一开始用X，整个函数都用X)
      * b: 用于构造子序列的二维数组
    */
    public static void lcs(int i, int j, char[] x, int[][] b)
    {
        if(i == 0 || j == 0)
            return;
        if(b[i][j] == 1)
        {
            lcs(i - 1, j - 1, x, b);
            System.out.print(x[i] + " ");
        }
        else if(b[i][j] == 2)
            lcs(i - 1, j, x, b);
        else
            lcs(i, j - 1, x, b);
    }
}

运行结果

结果示例