题解 | #70.兑换零钱(一)#

一开始没看懂dp方程，

举个例子，假如现在我们要求10元所需要的货币，

此时面值有[1，2，4，7，18，22]

显然无法用18和22参与兑换，因此有arr[j]<=i这个限定条件

10元可以

• 由9元所需货币数加上1元面值
• 由8元所需货币数加上2元面值
• 由7元所需货币数加上3元面值
• 由6元所需货币数加上4元面值
• 由5元所需货币数加上5元面值
• 由4元所需货币数加上6元面值
• 由3元所需货币数加上7元面值
• 由2元所需货币数加上8元面值
• 由1元所需货币数加上9元面值

因此，$dp[i]=min(dp[i],dp[i-arr[j]]+1)dp[i]\; =\; min(dp[i],dp[\; i-arr[j]\; ]+1)$

这里的1就表示用arr[j]面值的货币

function minMoney( arr ,  aim ) {
  
  let dp = new Array(aim+1);
  
  //初始化dp
  for(let i=1; i<=aim; i++)
    dp[i] = Infinity;
  dp[0] = 0;
  
  //dp[i]表示钱数为i时的最少货币数
  //比如当前面额为10 面额为7需要2个货币，面额为8需要111个货币，  
  //dp[10] = (dp[10],dp[7]+1,dp[8]+1,dp[6]+1)...
  
  for(let i=1; i<=aim; i++){//钱从1-aim
    for(let j=0; j<arr.length; j++){//遍历钱币
      if(arr[j] <= i){//如果当前的钱币比目标值小就可以兑换
        dp[i] = Math.min( dp[i], dp[i-arr[j]] + 1);
      }
    }
  }
  return dp[aim] > aim ? -1:dp[aim];
}