动态规划

　　动态规划（Dynamic Programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化算法。下面有一些用动态规划来解决实际问题的算法：

最少硬币找零

　　给定一组硬币的面额，以及要找零的钱数，计算出符合找零钱数的最少硬币数量。例如，美国硬币面额有1、5、10、25这四种面额，如果要找36美分的零钱，则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。

　　对于每一种面额，我们都分别计算所需要的硬币数量。具体算法如下：

  1. 如果全部用1美分的硬币，一共需要36个硬币
  2. 如果用5美分的硬币，则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币
  3. 如果用10美分的硬币，则需要3个10美分的硬币 + 1个5美分的硬币 + 1个1美分的硬币 = 5个硬币
  4. 如果用25美分的硬币，则需要1个25美分的硬币 + 1个10美分的硬币 + 1个1美分的硬币 = 3个硬币

　　对应的示意图如下：

　　方案4的硬币总数最少，因此为最优方案。

　　具体的代码实现如下：

复制代码
function minCoinChange(coins, amount) {     let result = null;     if (!amount) return result;      const makeChange = (index, value, min) => {         let coin = coins[index];         let newAmount = Math.floor(value / coin);         if (newAmount) min[coin] = newAmount;         if (value % coin !== 0) {             makeChange(--index, value - coin * newAmount, min);         }     };      const arr = [];     for (let i = 0; i < coins.length; i++) {         const cache = {};         makeChange(i, amount, cache);         arr.push(cache);     }      console.log(arr);     let newMin = 0;     arr.forEach(item => {         let min = 0;         for (let v in item) min += item[v];         if (!newMin || min < newMin) {             newMin = min;             result = item;         }     });     return result; }
复制代码

　　函数minCoinChange()接收一组硬币的面额，以及要找零的钱数。我们将上面例子中的值传入：

const result = minCoinChange2([1, 5, 10, 25], 36); console.log(result);

　　得到如下结果：

复制代码
[   { '1': 36 },   { '1': 1, '5': 7 },   { '1': 1, '5': 1, '10': 3 },   { '1': 1, '10': 1, '25': 1 } ] { '