LeetCode 322. 零钱兑换

[Chocolate1999]

仰望星空的人，不应该被嘲笑

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

输入：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 。

/**
 * @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]; // 如果还是无穷大，那么就找不到对应的硬币组合
};

最后

文章产出不易，还望各位小伙伴们支持一波！

往期精选：

小狮子前端の笔记仓库

leetcode-javascript：LeetCode 力扣的 JavaScript 解题仓库，前端刷题路线（思维导图）

小伙伴们可以在Issues中提交自己的解题代码，🤝 欢迎Contributing，可打卡刷题，Give a ⭐️ if this project helped you!

访问超逸の博客，方便小伙伴阅读玩耍~

学如逆水行舟，不进则退