动态规划（dynamic programming）是一种将复杂问题分解成更小的子问题来解决的优化技术。

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

  1. 定义子问题。
  2. 实现要反复执行来解决子问题的部分。
  3. 识别并求解出基线条件(不再递归调用的条件->停止点)。

最少硬币找零问题

最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可用的硬币面额d1，…，dn及其数量，找出有多少种找零方法。最少硬币找零问题时给出要找零的钱数，以及可用的硬币面额
d1，…，dn及其数量，找到所需的最好的硬币个数。
例如：美国有以下的面额硬币：d1 = 1, d2 = 5, d3 = 10,d4 = 25。
如果要找36美分的零钱，我们可以用1个25美分，1个10美分，和1美分。
如何将这个解答转化成算法。
最少硬币找零的解决方法是找到n所需的最小的硬币数。

  1. function minCoinChange(coins,amount){
  2.     const cache = [];
  4.     const makeChange = (value) => {
  5.         if(!value){
  6.             return [];
  7.         }
  9.         if(cache[value]){
  10.             return cache[value];
  11.         }
  13.         let min = [];
  14.         let newMin;
  15.         let newAmount;
  16.         for(let i = 0; i < coins.length; i++){
  17.             const coin = coins[i];
  18.             newAmount = value - coin;
  19.             if(newAmount >= 0){
  20.                 newMin = makeChange(newAmount);
  21.             }
  22.             if(newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)){
  23.                 min = [coin].concat(newMin);
  24.                 console.log(`new Min ${min} for ${value}`);
  25.             }
  26.         }
  27.         return (cache[value] = min);
  28.     }
  29.     return makeChange(amount);
  30. }
  32. console.log(minCoinChange([1,5,10,25],36));

题解再补