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

  • 动态规划最长公共子序列(LCS)问题(Java实现)
  • 问题分析
  • Java代码实现

携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第9天,点击查看活动详情

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

首先,明白一个公共子序列和公共子串的区别

  • 公共子序列: 可以不连续
  • 公共子串: 必须连续

问题分析


  1. 求最长公共子序列,先明白两个概念

    • 子序列
      • 一个给定序列中删去若干元素后得到的序列
    • 公共子序列
      • 给定两个序列X,Y,当另一序列Z 既是X 的子序列,又是Y 的子序列时,就称Z 为X、Y 的公共子序列
  2. 明白上述两个概念后,我们就可以开始搜索最长公共子序列

    • 这个问题可以使用暴力方法解决,但是由于要全部搜索一遍,时间复杂度为 O(n2m),所以我们不采用
    • 我们可以使用动态规划算法,自底向上进行搜索,这样,在计算后面的时候,前面的数据我们已经对其进行保存,直接进行计算即可,时间复杂度很大程度降低。
  3. 既然决定使用动态规划算法,首先引入一个二位数组 c[][], 记录 x[i] 与 y[j] 的LCS 的长度,b[i][j] 记录 c[i][j] 的通过哪一个子问题的值求得的,以决定搜索方向。

  4. 抽取状态转移方程(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,有两种情况
      1. Zk ≠ Xm,那么Z 一定是Xm-1, Y 的一个公共子序列,
      2. Zk ≠ Yn,那么Z 一定是X, Yn-1 的一个公共子序列
    • 这样,第三种情况我们就可以表示成: c[i][j] = max{c[i-1][j], c[i][j-1]}
    • 那么,我们就可以写出其状态转移方程

image.png

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; 
	}
	*/
}

原文:https://juejin.cn/post/7128574834543427621
版权声明:本文内容由TeHub注册用户自发贡献,版权归原作者所有,TeHub社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《TeHub社区用户服务协议》和《TeHub社区知识产权保护指引》。 如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
喜欢(0)
chris
啥也不会的站长。

评论(0)

添加评论