image.png

思路

我目前总结一个规则就是：题目求什么，dp的含义其实就是什么！别自己多想了！
这道题dp就是指 凑成amount所需的最少个数。
然后！去思考怎么得到dp，得到dp[j]（考虑coins[i]），只有一个来源，dp[j - coins[i]]（没有考虑coins[i]）。
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
这道题是之前都没碰到过一种情况，求的是最小值。所以初始化有点不同，请看
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
其他下标对应的数值呢？
考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

  1. var coinChange = function(coins, amount) {
  2.     //dp是凑足amount所需最少的个数
  3.     //这道题求最小，所以初始化infinity，但dp[0]=0
  4.     let dp =new Array(amount+1).fill(Infinity) 
  5.     dp[0] =0
  6.     if(amount===0) return 0
  9.     for(let i=0;i<coins.length;i++){
  10.         for(let j=coins[i];j<=amount;j++){
  11.             dp[j] =Math.min(dp[j],dp[j-coins[i]]+1)
  12.         }
  13.     }
  15.     return dp[amount] ===Infinity? -1:dp[amount]
  16. };