基于JavaScript的递归算法题和动态规划题目

前记：

这世界上总存在着那么一些看似相似但有完全不同的东西，比如雷锋和雷峰塔，玛丽和马里奥，Java和javascript….当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子，哦，不是应该是跪舔，毕竟都跟了Java的姓了。可如今，javascript来了个咸鱼翻身，几乎要统治web领域，Nodejs，React Native的出现使得javascript在后端和移动端都开始占有了一席之地。

之前已经有同学讲过了递归和动态规划之间的关系。今天，我们就再来温习一遍。简单的讲述一下递归和动态规划的一些题目。今天主要就是它们是如何用JavaScript来实现的！打破常规，不单单是能用C和JAVA来a题。也能让我们这些学习前端的同学好好的使用JS来A题。

递归算法

递归的定义：

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

简单来说：递归算法，是将问题转化为规模缩小的同类问题的子问题，每一个子问题都用一个同样的算法去解决。一般来说，一个递归算法就是函数调用自身去解决它的子问题

递归的特点：

             1）递归就是方法里调用自身。   
             2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。    
             3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
             4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

例题1：

小试牛刀：汉诺塔

"汉诺塔"是印度的一个古老传说，也是程序设计中的经典的递归问题，是一个著名的益智游戏：

　　题目如下：

　　　　塔上有三根柱子和一套直径各不相同的空心圆盘，开始时源柱子上的所有圆盘都按从大到小的顺序排列。目标是通过每一次移动一个圆盘到另一根柱子上，最终把一堆圆盘移动到目标柱子上，过程中不允许把较大的圆盘放置在较小的圆盘上。

规律：

　　1）n(圆盘个数) == 1

　　　　第一次：1号盘  A -> C      sum(移动次数) = 1

　　2）n == 2

　　　　第一次：1号盘 A -> B

　　　　第二次：2号盘 A -> C

　　　　第三次：1号盘 B -> C　　sum = 3

　　3）n == 3

　　　　第一次：1号盘 A -> C

　　　　第二次：2号盘 A -> B

　　　　第三次：1号盘 C -> B

　　　　第四次：3号盘 A -> C

　　　　第五次：1号盘 B -> A

　　　　第六次：2号盘 B -> C

　　　　第七次：1号盘 A -> C　　sum = 7

　　以此类推...

　　故不难发现规律,移动次数为：sum = 2^n - 1　

 

分析：

　　把一堆圆盘从一个柱子移动另一根柱子，必要时使用辅助的柱子。可以把它分为三个子问题：

　　　　首先，移动一对圆盘中较小的圆盘到辅助柱子上，从而露出下面较大的圆盘，

　　　　其次，移动下面的圆盘到目标柱子上

　　　　最后，将刚才较小的圆盘从辅助柱子上在移动到目标柱子上

　　 把三个步骤转化为简单数学问题：

　　　　（1）     把 n-1个盘子由A 移到 B；

　　　　（2）     把 第n个盘子由 A移到 C；

　　　　（3）     把n-1个盘子由B 移到 C；

　　我们创建一个JS函数，当它调用自身的时候，它去处理当前正在处理圆盘之上的圆盘。最后它回一个不存在圆盘去调用，在这种情况下，它不在执行任何操作

下面上JS代码：

/*汉诺塔函数*/
		function hanoi(disc,src,aux,dst){
		    if(disc>0){
		        hanoi(disc-1,src,dst,aux);
		        console.log(' 移动 '+ disc +  ' 号圆盘 ' + ' 从 ' + src +  ' 移动到 ' +  dst);
		        // hanoi(disc,src,aux,dst); // 栈溢出
		        hanoi(disc-1,aux,src,dst)
		    }
		}

 

 例题2：

    走楼梯：（问题描述）

    楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶或者3阶，计算共有多少种不同的走法？（注意，例如：3阶楼梯4种方法：1. 一步一步一步 2.一步两步 3.三步 4.两步一步）

 

 分析：

这其实就是一个斐波那契数列的一种实现。我们分析的时候，可以转化成小规模的子类问题。当到达指定阶梯的最后一步的时候，可以有三种种情况，一是上一步，二是上两步，三是上三步。所以总的方法是F(n) = F(n-1) + F(n-2) + F(n-3)。然后自然就成了各自的小计算，不断循环下去，直到判断条件的发生。

下面上代码

/*走楼梯问题*/
		function getMethods(n) {
			if (n <= 0) {
				return 0;
			}
			if (n <= 1) {
				return 1;
			}
			if (n <= 2) {
				return 2;
			}
			if (n <= 3) {
				return 4;
			}
			return arguments.callee(n-1) + arguments.callee(n-2) + arguments.callee(n-3);
		}
console.log(getMethods(5));

 注意：argument.callee

 

在函数内部，有两个特殊的对象：arguments 和 this。其中， arguments 的主要用途是保存函数参数， 但这个对象还有一个名叫 callee 的属性，该属性是一个指针，指向拥有这个 arguments 对象的函数。一般来说，它会和匿名函数一起结合来用。但是不建议使用，因为访问 arguments 是个很昂贵的操作，因为它是个很大的对象，每次递归调用时都需要重新创建。影响现代浏览器的性能，还会影响闭包。

例题3：（具有JS特色的递归）

DOM树的递归：（问题描述）

获取一个节点的所有父节点的tagName

比较简单就直接上代码了：

/*DOM树的递归问题*/
		var arr = [];  
		function getParent(node) {  
		    node = node.parentNode;  
		    if (node.tagName) {  
		        arr.push(node.tagName);  
		        getParent(node);  
		    }  
		}  
		getParent(document.getElementById("node"));  
		console.log(arr); 

 到此呢，递归就告一段落，希望大家能有更深的理解。虽然题目都是最基本的，但是我们通过打断点，能发现这个代码执行的步骤，也理解什么时候该执行什么。便于我们理解吧！

 

动态规划：

动态规划也是五大常用算法之一（贪婪算法，动态规划，分治算法，回溯，分支限界）。

基本思想：

它的思想就是把一个大的问题进行拆分，细分成一个个小的子问题，且能够从这些小的子问题的解当中推导出原问题的解。同时还需要满足以下两个重要性质才能进行动态规划

• 最优子结构性: 既所拆分的子问题的解是最优解。

• 子问题重叠性质: 既在求解的过程当中，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率

我认为，上面讲的楼梯问题，也算是动态规划的一种，自底向上，只考虑这0阶楼梯，1阶楼梯，2阶楼梯，3阶楼梯。总方案数都是由，0种方案，1种方案，2种方案，4种方案这四个数字加起来的。话不多说，我们看一个例子吧。

例子1：

最长公共子串：

问题描述：什么是最长公共子串呢？举个简单的例子吧，一个数列S，若分别是两个或多个已知序列的子序列，且是所有符合条件序列中最长的，则S称为已知序列的最长公共子串。

举例：比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2

解决方法：

蛮力法：即对S的每一个子序列，检查是否为T的子序列，从而确定它是否为S和T的公共子序列，并且选出最长的公共子序列。指数级别的时间复杂度o(2^n*2^m)n和m代表两个序列的长度。

当然，我们也可以使用动态规划的方法！

动态规划方法的分析：

1. 假设两个字符串分别为s和t，s[i]和t[j]分别表示其第i和第j个字符(字符顺序从0开始)，再令L[i, j]表示以s[i]和t[j]为结尾的相同子串的最大长度。应该不难递推出L[i, j]和L[i+1,j+1]之间的关系，因为两者其实只差s[i+1]和t[j+1]这一对字符。若s[i+1]和t[j+1]不同，那么L[i+1, j+1]自然应该是0，因为任何以它们为结尾的子串都不可能完全相同；而如果s[i+1]和t[j+1]相同，那么就只要在以s[i]和t[j]结尾的最长相同子串之后分别添上这两个字符即可，这样就可以让长度增加一位。合并上述两种情况，也就得到L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)这样的关系。

   最后就是要小心的就是临界位置：如若两个字符串中任何一个是空串，那么最长公共子串的长度只能是0；当i为0时，L[0,j]应该是等于L[-1,j-1]再加上s[0]和t[j]提供的值，但L[-1,j-1]本是无效，但可以视s[-1]是空字符也就变成了前面一种临界情况，这样就可知L[-1,j-1]==0，所以L[0,j]=(s[0]==t[j]?1:0)。对于j为0也是一样的，同样可得L[i,0]=(s[i]==t[0]?1:0)

下面上代码：

<script type="text/javascript">
                /*最长子串*/
		var str1="abcdefghijklname123what";  
		var str2="defghiwhatisyourname";  
		var L=[];//备忘录 记录L[i][j]最大长度子串L[i][j]=max(L[i-1][j-1]+1,0)  
		getMaxSubStr();  
		function getMaxSubStr(){  
		   for (var i=0;i<str1.length+1;i++)  
		   {  
		     L[i]=[];  
		     L[i][0]=0;  
		   }  
		   for (var j=0;j<str2.length+1;j++ )  
		   {   
		     L[0][j]=0;  
		   }  
		   var max=-1;  
		   var x=-1;  
		   var y=-1;  
		   for (var i=1;i<str1.length+1;i++ )  
		   {  
		      for (var j=1;j<str2.length+1;j++ )  
		      {  
		         //alert(str1[i-1]+":"+str2[j-1]);  
		         if(str1.charAt(i-1)==str2.charAt(j-1)){  
		            L[i][j]=L[i-1][j-1]+1;  
		         }  
		         else{  
		            L[i][j]=0;  
		         }  
		           
		         //document.write(L[i][j]);  
		         if(L[i][j]>max){  
		            max=L[i][j];  
		            x=i-1;  
		            y=j-1;  
		            document.write("i="+i+";j="+j+";max="+max+"<br/>");  
		         }  
		      }  
		   }  
		   //输出共同的子串  
		   var str=[];  
		   while(x>=0&&y>=0){  
		      if(str1.charAt(x)==str2.charAt(y)){  
		         str[--max]=str1.charAt(x);  
		         x--;  
		         y--;  
		      }  
		      else  
		         break;  
		   }  
		   var str_out="";  
		   for (var i=0;i<str.length;i++ )  
		   {  
		     str_out+=str[i];  
		   }  
		   document.write(str_out);  
		} 
	</script>

 到这呢，基本就结束了。

 有什么意见请多批评指教！