详解动态规划最长公共子序列--JavaScript实现

栏目: 编程工具 · 发布时间: 6年前

内容简介:前面两篇我们讲解了01背包问题和最少硬币找零问题。这篇将介绍另一个经典的动态规划问题--最长公共子序列。如果没看过前两篇,可点击下面链接。

前面两篇我们讲解了01背包问题和最少硬币找零问题。这篇将介绍另一个经典的动态规划问题--最长公共子序列。如果没看过前两篇,可点击下面链接。

详解动态规划最少硬币找零问题--JavaScript实现

详解动态规划01背包问题--JavaScript实现

问题

给定两个字符串序列 abcadf , acbad ,求这两个字符串的最长公共子序列

分析

最长公共子序列问题,有三个点需要注意

  • 两个序列长度不一定相同
  • 最长子序列是指,在两个字符串序列中以相同顺序出现
  • 所求的子序列不需要连续

在进行填表分析之前,根据上面提到的三个点,我们可以很容易地先直接得出答案,最长公共子序列应为 acad

1. 建表

我们给两个子序列前面都加一个空字符,即

input1 = ["","a","c","b","a","d"],
input2 = ["","a","b","c","a","d","f"],

然后构建如下表格

详解动态规划最长公共子序列--JavaScript实现

为什么填一堆0呢?表示字符串无法匹配,你可以理解这是一种辅助的计算方式, 在分析具体子序列时,不把构建的空字符纳入考虑范围 。在后面也会按照前面2篇的思路,使用 T[i][j] 表示组合的子序列长度。

下面将从左往右,从上往下开始填表。我们在填写某一个表格的时候,只需要考虑小于等于i 和小于等于j的情况。比如我们要填写T[2][2]时,那么此时等同于求字符串 ac , ab 的最长公共子序列,填写T[4][5]时,那么此时等同于求 acbaabcad 的最长公共子序列长度。

如果你看过前两篇,对于这种填表应该会很熟悉。 下面基于这个表格,开始填表。

2. i =1

我们从第一行开始。

i=1 j=1 :此时等同于求字符串 aa 的最长公共子序列长度,很显然结果为1。

i=1 j=2 :此时等同于求字符串 aab 的最长公共子序列长度,结果为1。

i=1 j=3 :此时等同于求字符串 aabc 的最长公共子序列长度,结果为1。

只要一个序列只有一个字符,那么另一个序列无论多长,它们的最长公共子序列长度最多只能为1。所以 i=1 行剩余空格都填1。

详解动态规划最长公共子序列--JavaScript实现

3. i = 2

i=2 j=1 :此时等同于求字符串 aca 的最长公共子序列长度,结果为1。

i=2 j=2 :此时等同于求字符串 acab 的最长公共子序列长度,结果为1。

i=2 j=3 :此时等同于求字符串 acabc 的最长公共子序列长度。这时就有意思了。因为根据一开始的分析,求最长公共子序列时,子序列是可以不连续的,因此这两个序列的最长公共子序列应该是 ac ,所以这里表格应该填2。

详解动态规划最长公共子序列--JavaScript实现

好了,停下,先不用急着继续填,我们需要先分析一下通用思路。

4.填表思路

我们从T[2][3]=2 这一个格分析。很显然去除 c 这个公共字符后,两个字符串还剩下 a , ab 。是不是有点熟悉?这个其实就是填写 T[1][2] 时的组合,也就是我们可以假设当 input1[i] == input2[j] 时, T[i][j]=T[i-1][j-1] 。 当 input1[i] != input2[j] 时, T[i][j] 的值,取它上方或左边的较大值,即 [i][j] = max(T[i-1][j],T[i][j-1])

用一句通俗的话来描述这种 T[i][j] 规律,就是 相等左上角加一,不等取上或左最大值,如果上左一样大,优先取左。

好了,不看下面内容,你带着这种规律,把表格剩余内容自己填写完毕。

5.最终表格

理解了这种规律,我们没必要把每一格该怎么填重复叙述了。下面就是最终表格。

详解动态规划最长公共子序列--JavaScript实现

我们举个例子,比如 i=5 j=4,此时 input1[i] !=input2[j] ,我们取它左边(2)或者上方(3)的较大值,所以填写3。

i=5 j=5,此时 input1[i] ==input2[j] ,我们直接取左上角值加1,左上角的值为T[4][4]=3,所以T[5][5]=4 。

如果还不太理解,可以自己再练习画一次。

6.寻找子串

我们完成填表后,只能求出最长公共子序列的长度,但是无法得知它的具体构成。我们可以参照上一篇硬币问题,从填表的反向角度来寻找子序列。

我们子序列保存在名为 s的数组中,从表格中反向搜索,找到目标字符后,每次都把目标字符插入到数组最前面。

根据前面提供的填表口诀,我们可以反向得出寻找子序列的口诀: 如果T[i][j]来自左上角加一,则是子序列,否则向左或上回退。如果上左一样大,优先取左。

1.从右下角开始分析,T[5][6]=4,它并不是来自左上角。它左边的值比上方大,所以它来自左边,向左回退,如下图箭头。

详解动态规划最长公共子序列--JavaScript实现

2.接着就定位到 T[5][5],显然他来自左上角加1,它是子序列。插入数组中,有

s = ['d']

3.扣除掉 T[5][5],可以定位到它的左上角 T[4][4],如图:

详解动态规划最长公共子序列--JavaScript实现

T[4][4]也是来自左上角加1,它也是子序列,把它插入到数组最前面,此时 s 应该是

s = ['a','d']

4.按照前面的思路,继续定位分析,最终如下图:

详解动态规划最长公共子序列--JavaScript实现

最终箭头指向0,搜索结束。

s = ['a','b','a','d']

伪代码

整个分析过程已经完成了。下面提供代码逻辑,即使不懂 JavaScript,也不会影响你理解,因为没有涉及语言特性。

填表

if(input1[i] == input2[j]){
	T[i][j] = T[i-1][j-1] + 1;
}else{
	T[i][j] = max(T[i-1][j],T[i][j-1])
}

寻找子串

if(input1[i] == input2[j]){
	s.insertToIndexZero(input1[i]); //插入到数组最前面
	i--;
	j--;
}else{
	//向左或向上回退
	if(T[i-1][j]>T[i][j-1]){
		//向上回退
		i--;
	}else{
		//向左回退
		j--;
	}
}

完整代码

最终代码使用 JavaScript 实现,如果你的 Sublime 支持纯 JavaScript,你可以直接复制黏贴代码,command + b 直接运行查看结果,然后修改输入变量,查看更多情况下的输出结果。

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


//!!!!  T[i][j] 计算,记住口诀:相等左上角加一,不等取上或左最大值

function longestSeq(input1,input2,n1,n2){
	var T = []; // T[i][j]表示 公共子序列长度
	for(let i=0;i<n1;i++){
		T[i] = [];
		for(let j= 0;j<n2;j++){
			if(j==0 ||i==0){
				T[i][j] = 0;
				continue;
			}
			if(input1[i] == input2[j]){
				T[i][j] = T[i-1][j-1] + 1;
			}else{
				T[i][j] = Math.max(T[i-1][j],T[i][j-1])
			}

		}

	}

	findValue(input1,input2,n1,n2,T);

	return T;

}

//!!!如果它来自左上角加一,则是子序列,否则向左或上回退。
//findValue过程,其实就是和 就是把T[i][j]的计算反过来。
function findValue(input1,input2,n1,n2,T){
	var i = n1-1,j=n2-1;
	var result = [];//结果保存在数组中
	console.log(i);
	console.log(j);
	while(i>0 && j>0){
		if(input1[i] == input2[j]){
			result.unshift(input1[i]);
			i--;
			j--;
		}else{
			//向左或向上回退
			if(T[i-1][j]>T[i][j-1]){
				//向上回退
				i--;
			}else{
				//向左回退
				j--;
			}
		}

	}

	console.log(result);
}


//两个序列,长度不一定相等, 从计算表格考虑,把input1和input2首位都补一个用于占位的空字符串
var input2 = ["","a","b","c","a","d","f"],
	input1 = ["","a","c","b","a","d"],
	n1 = input1.length,
	n2 = input2.length;

console.log(longestSeq(input1,input2,n1,n2));

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

学习JavaScript数据结构与算法(第2版)

学习JavaScript数据结构与算法(第2版)

[巴西] Loiane Groner / 邓 钢、孙晓博、吴 双、陈 迪、袁 源 / 人民邮电出版社 / 2017-9 / 49.00元

本书首先介绍了JavaScript 语言的基础知识以及ES6 和ES7 中引入的新功能,接下来讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构,之后探讨了各种排序和搜索算法,包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序、顺序搜索、二分搜索,然后介绍了动态规划和贪心算法等常用的高级算法以及函数式编程,最后还介绍了如何计算算法的复杂度。一起来看看 《学习JavaScript数据结构与算法(第2版)》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

URL 编码/解码
URL 编码/解码

URL 编码/解码