零钱兑换

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

  • 输入:coins = [1, 2, 5], amount = 11
    输出:3
    解释:11 = 5 + 5 + 1

  • 输入:coins = [2], amount = 3
    输出:-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var coinChange = function(coins, amount) {
// 初始化一个dp数组,为了方便初始化为Infinity,其实大于amount的都行吧
let dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // 面额为0的需要0个硬币兑换

for(let i = 1; i <= amount; i++) { // 循环面额
for(let coin of coins) { // 循环硬币数组
if(i >= coin) { // 当面额大于硬币价值时
// dp[i - coin]:当前面额i减当前硬币价格所需要的最少硬币
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// 如果dp[amount]为Infinity,则无法兑换
return dp[amount] === Infinity ? -1 : dp[amount];
};