最值问题是动态规划常见的题型

    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1

    示例：
    输入：coins =[ 1,2,5]，amout = 11
    输出：3 （5+5+1）
    输入：coins= [2], amout = 3
    输出：-1
    思路分析：
    这道题的难点在于分析状态转移方程，尽管动态规划的实现是自底向上的，分析时却可以借鉴递归自顶向下进行倒推。假设amout =10 ,coins =[1, 2, 5]，f(n)表示找零n的最小硬币个数，我们可以得到：

    1. f(10) = Math.min(f(9)+1, f(8)+1, f(5)+1)

    这样就可以推断出状态转移方程的形态，
    同时 f(0) = 0，相当于初始条件

    1. /**
    2.  * 找硬币所需最少硬币个数
    3.  */
    4. const coinChange = function(coins, amount){
    5.   const cache = [] // 缓存每个总额对应的最少硬币数
    6.   cache[0] = 0 // 初始条件
    7.   for(let i=1; i<=amount; i++){
    8.     // 用极大值初始化，便于用小值更新
    9.     cache[i] = Infinity 
    10.     for(let j=0; j< coins.length;j++){ // 每种硬币都试试
    11.       if(i - coins[j] >= 0){
    12.         // 状态转移方程
    13.         cache[i] = Math.min(cache[i], cache[i-coins[j]] + 1)// 
    14.       }
    15.     }
    16.   }
    17.   if(cache[amount] === Infinity){ // 表示cache[amount] 一直没有更新过，无解
    18.     return -1
    19.   }
    20.   return cache[amount]
    21. }