ChoDocs

外观

LeetCode 322. 零钱兑换 ​

作者:Choi Yang
更新于:7 个月前
字数统计:489 字
阅读时长:1 分钟

题目描述 ​

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

你可以认为每种硬币的数量是无限的。

示例 1：

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

示例 2：

javascript
输入：coins = [2], amount = 3
输出：-1

示例 3：

javascript
输入：coins = [1], amount = 0
输出：0

示例 4：

javascript
输入：coins = [1], amount = 1
输出：1

示例 5：

javascript
输入：coins = [1], amount = 2
输出：2

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 231 - 1

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-change 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

对于零钱兑换问题，本题不能用贪心来做，要用 dp，状态方程如下代码。

我们首先将数组都初始化为正无穷，对于 0 ，默认为 0 即可，不需要兑换硬币，然后从 1 迭代到 amount ，如果当前金额，可以减去当前硬币的价值，拿当前硬币，然后我们求最小的硬币数。

最后，如果还是无穷大，那么就找不到对应的硬币组合，直接输出 -1 。

javascript
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  let dp = new Array(amount + 1).fill(Infinity); // 初始化都为无穷大
  dp[0] = 0; // 没钱时不需要硬币
  for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      if (i - coin >= 0)
        // 如果当前金额，可以减去当前硬币的价值，拿当前硬币
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] == Infinity ? -1 : dp[amount]; // 如果还是无穷大，那么就找不到对应的硬币组合
};
javascript
学如逆水行舟，不进则退

Contributors ​

Choi Yang