本文共 1311 字，大约阅读时间需要 4 分钟。

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

题目描述

给定不同面额的硬币 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）

解题思路

对于零钱兑换问题，本题不能用贪心来做，要用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]; // 如果还是无穷大，那么就找不到对应的硬币组合};

最后

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

往期精选：

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

，方便小伙伴阅读玩耍~

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/108940211 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！