本文转载自微信公众号《JS日报》，作者灰灰。转载本文请联系JS每日一问公众号。1.贪心算法贪心算法，又称贪心算法，是算法设计中的一种思想。它期望每个阶段都是局部最优选择，从而达到全局最优，但结果不一定是最优的。举个零钱兑换的例子，如果你有1元、2元、5元的硬币，分别用来兑换一定数量的硬币，但是需要兑换的硬币数量最少，如果你要兑换11元现在，按照贪心算法的思路，先选择面额最大的5元硬币进行兑换，那么就会得到11=5+5+1的选择，这种情况是最优的，但是如果你手上的硬币面额分别是1、3、4，你要兑换6元，根据贪心算法的思想，我们会选择6=4+1+1。本例结果为不是最佳选择。从上面的例子我们可以看出贪心算法有一些缺点。在使用贪心算法时，会有一个特点：一旦一个问题可以用贪心法解决，那么一般来说贪心法就是解决这个问题的最好方法。至于是否选择贪心算法，主要看它是否具有以下两个特点：通过一系列的局部最优解选择可以得到整体最优解，每次做出的选择都可以依赖于之前的选择，但不需要依赖于以后需要做出的选择。最优子结构：如果一个问题的最优解包含它的子问题的最优解，那么这个问题就具有最优子结构的性质。问题的最优子结构是问题能否被贪心算法解决的关键。2.回溯算法回溯算法也是算法设计中的一种思想。是一种策略性的回溯算法，逐步寻找并构建问题的解决方案会从一个可能的工作开始解决问题，如果没有，回头再选择另一个动作，直到使用回溯算法解决问题，有如下特点：路径有很多种，比如矩阵的方向或者树的路径在这些路径中，有死胡同，也有人生路径。思路是不符合题目要求的路径，生存路径符合平时用递归模拟所有路径。常见的伪代码如下：result=[]functionbacktrack(path,selectionlist):结束条件：result.add(path)returnforselectionselectionlist:makeselectionbacktrack(path,selectionlist)undoselection重点解决三problems:路径：即已经做出的选择列表结束条件例如经典的回溯算法，为了解决全排列问题，如下：一个没有重复数的数组nums，我们要返回所有可能的完整排列。解决这个问题的思路是：用递归模拟所有情况，遇到重复元素回溯收集所有递归结束的情况，返回，用代码表示如下：varpermute=function(nums){constres=[],path=[];backtracking(nums,nums.length,[]);returnres;functionbacktracking(n,k,used){if(path.length===k){res.push(Array.from(path));return;}for(leti=0;i
