动态规划最长公共子序列（LCS）问题（Java 实现）

若尘

关注

发布于: 2021 年 06 月 10 日

动态规划最长公共子序列（LCS）问题（Java 实现）

首先，明白一个公共子序列和公共子串的区别
公共子序列： 可以不连续
公共子串： 必须连续

问题分析

求最长公共子序列，先明白两个概念
子序列
一个给定序列中删去若干元素后得到的序列
公共子序列
给定两个序列 X，Y，当另一序列 Z 既是 X 的子序列，又是 Y 的子序列时，就称 Z 为 X、Y 的公共子序列
明白上述两个概念后，我们就可以开始搜索最长公共子序列
这个问题可以使用暴力方法解决，但是由于要全部搜索一遍，时间复杂度为 O(n2m)，所以我们不采用
我们可以使用动态规划算法，自底向上进行搜索，这样，在计算后面的时候，前面的数据我们已经对其进行保存，直接进行计算即可，时间复杂度很大程度降低。
既然决定使用动态规划算法，首先引入一个二位数组 c[][], 记录 x[i] 与 y[j] 的 LCS 的长度，b[i][j] 记录 c[i][j] 的通过哪一个子问题的值求得的，以决定搜索方向。
抽取状态转移方程（X=x1x2...xm、Y=y1y2...yn为两个序列，Z=z1z2...zk为公共子序列）
对于 x[i] 和 y[j], 若 i = 0 or j = 0，显然，c[i][j] = 0
若 i = j，我们可以使用上一步计算的值直接进行计算，即 c[i][j] = c[i-1][j-1] + 1
若 i ≠ j，有两种情况
Zk ≠ Xm，那么 Z 一定是 Xm-1, Y 的一个公共子序列,
Zk ≠ Yn，那么 Z 一定是 X, Yn-1 的一个公共子序列
这样，第三种情况我们就可以表示成： c[i][j] = max{c[i-1][j], c[i][j-1]}
那么，我们就可以写出其状态转移方程

c [i] [j] = {0 i = 0 ， o r ， j = 0 \c [i - 1] [j - 1] + 1 x [i] = y [j] max c [i - 1] [j], c [i] [j - 1] x [i] \neq = y [j]

Java 代码实现

/* * 若尘 */package lsc;
/** * 最长公共子序列  * @author ruochen * @version 1.0 */public class LSCProblem {      /** lcs 用来保存最优解 */    private static String lcs = "";
  public static void main(String[] args) {    String str1 = "ABCDBC";    String str2 = "ABCEAC";        String[] x = strToArray(str1);    String[] y = strToArray(str2);        int[][] b = getSearchRoad(x, y);        Display(b, x, x.length - 1, y.length - 1);    System.out.println("lcs： " + lcs);    System.out.println("len: " + lcs.length());  }      /**   *    * @param str   * @return   */  public static String[] strToArray(String str) {    String[] strArray = new String[str.length() + 1];    strArray[0] = "";    for (int i = 1; i < strArray.length; i++) {      strArray[i] = ""+str.charAt(i - 1);    }    return strArray;  }    /**   * 计算最长子序列长度以及记录最优解数组   * @param x 序列1   * @param y 序列2   * @return 返回一个可查询最优解的数组   */  public static int[][] getSearchRoad(String[] x, String[] y) {    int[][] b = new int[x.length][y.length];    int[][] c = new int[x.length][y.length];        // 第一行 or 第一列，x[i] or y[j] 为0, 对应 c[i][j] 赋值为0     for (int i = 0; i < x.length; i++) {      c[i][0] = 0;    }    for (int j = 0; j < y.length; j++) {      c[0][j] = 0;    }    for (int i = 1; i < x.length; i++) {      for (int j = 1; j < y.length; j++) {        if (x[i].equals(y[j])) {          c[i][j] = c[i-1][j-1] + 1;          // b[i][j] = 1 表示取决于左上方          b[i][j] = 1;        } else if (c[i-1][j] >= c[i][j-1]) {          // 此处因为还要记录b[i][j]，所以没有使用max函数          c[i][j-1] = c[i-1][j];          // b[i][j] = 0 表示取决于左边          b[i][j] = 0;        } else {          c[i][j] = c[i][j-1];          // b[i][j] = -1 表示取决于上边          b[i][j] = -1;        }      }    }    return b;  }    /**   * 自右下向左上回溯，输出最优解   * @param b   * @param x   * @param i   * @param j   */  public static void Display(int[][] b, String[] x, int i, int j) {    if (i == 0 || j == 0) {      return ;    }    if (b[i][j] == 1) {      Display(b, x, i - 1, j - 1);      lcs += x[i];    } else if (b[i][j] == 0) {      Display(b, x, i - 1, j);    } else if (b[i][j] == -1) {      Display(b, x, i, j - 1);    }  }    /**   * 返回两个数的较大值   * @param x 第一个数   * @param y 第二个数   * @return   */  /*  public static int max(int x, int y) {    return (x >= y) ? x : y;   }  */}

复制代码

发布于: 2021 年 06 月 10 日阅读数: 8

原文链接:【http://xie.infoq.cn/article/b9e0f71e9d08fe7f41a7dc8b6】。文章转载请联系作者。

若尘

关注

还未添加个人签名 2021.01.11 加入

还未添加个人简介

发布

暂无评论

创作场景

动态规划最长公共子序列（LCS）问题（Java 实现）

动态规划最长公共子序列（LCS）问题（Java 实现）

问题分析

Java 代码实现

若尘

评论