阅读目录

1. 我们也可以用非递归的方法实现

   function fib(num){     var n1 = 1,     n2 = 1,     n = 1;     for(var i = 3; i <= num; i++){         n = n1 + n2;         n1 = n2;         n2 = n;     }     return n; }

   为什么要用递归？是因为更快吗？其实并不，反而更慢。递归的好处在于更容易理解，并且它所需的代码量更少。然后在ES6中，因为有尾调用，可以加快递归的速度。总而言之，我们用递归，通常是因为它更容易解决问题。

   动态规划

   动态规划（Dynamic Programming,DP）是一种将复杂问题分解成更小的子问题来解决的优化技术。与分而治之不同的是，动态规划是将问题分解成相互依赖的子问题。

   用动态规划解决问题，要遵循三个步骤：

   1. 实现子问题。
   2. 实现要反复执行来解决子问题的部分
   3. 识别并求解出边界条件

   可以用动态规划解决一些著名的问题如下：

   • 背包问题：给出一组项目，各自有值和容量，目标是要找出总值最大的项目的集合。这个问题的限制是，总容量必须小于等于“背包”的容量。
   • 最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变）
   • 矩阵链相乘：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少）。相乘操作不会进行，解决方案是找到这些矩阵各自相乘的顺序。
   • 硬币找零：给出面额为d1...dn的一定数量的硬币和要找零的钱数，找出有多少种找零的方法。
   • 图的全源最短路径：对所有顶点对（u,v），找出顶点u到顶点v的最短路径。

   最少硬币找零问题

   最少硬币找零问题是硬币问题的一个变种。硬币找零问题是给出要找零的钱数，以及可以用的硬币面额d1...dn 及其数量，找出有多少种找零方法。最少硬币找零问题是要给出要找零的钱数以及可用的硬币面额d1...dn及其数量，找出所需的最少硬币个数。

   例如，美国有一下面额（硬币）：d₁=1,d₂=5,d₃=10,d₄=25

   如果要找36美分的零钱，我么可以用1个25美分，1个10美分和一个便士（1美分）

   如何将这个解答转化成算法？

   最少硬币找零的解决方案是找到n所需的最小硬币数。但要做到这一点，首先得找到对每个x<n的解。然后，我们将解建立在更小的值的基础上。

   function MinCoinChange(coins){     var coins = coins; // 零钱的面额     var cache = {}; // 缓存     this.makeChange = function(amount){ // 递归函数         var me = this;         if(!amount){ // 若金额总额小于0则返回空数组             return [];         }         if(cache[amount]){ // 若缓存中已有该计算结果，则直接返回              return cache[amount];         }         var min = [],newMin,newAmount;          for(var i = 0; i < coins.length; i++){             var coin = coins[i];             newAmount = amount - coin;             if(newAmount >= 0){                 newMin = me.makeChange(newAmount);                               }             if(newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)){                 min = [coin].concat(newMin);                 console.log('new Min '+ min + 'for '+ amount);             }         }         return (cache[amount] = min);     }     this.getCache = function(){         console.log(cache);     } }

   测试

   const minCoinChange = new MinCoinChange([1,5,10,25]); console.log(minCoinChange.makeChange(36)); /* new Min 1,1,1,1,1for 5 new Min 5for 5 new Min 1,5for 6 new Min 1,1,5for 7 new Min 1,1,1,5for 8 new Min 1,1,1,1,5for 9 new Min 1,1,1,1,1,5for 10 new Min 5,5for 10 new Min 10for 10 new Min 1,10for 11 new Min 1,1,10for 12 new Min 1,1,1,10for 13 new Min 1,1,1,1,10for 14 new Min 1,1,1,1,1,10for 15 new Min 5,10for 15 new Min 1,5