322. 零钱兑换
322. 零钱兑换
🟠 🔖 广度优先搜索
数组
动态规划
🔗 力扣
LeetCode
题目
You are given an integer array coins
representing coins of different denominations and an integer amount
representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1
.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Constraints:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
题目大意
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
解题思路
可以使用动态规化,定义一个数组dp
,其中dp[i]
表示凑齐金额i
所需的最少硬币数。
- 初始化数组
dp
为-666
,便于后续取最小值。 - 将 base case
dp[0]
设置为0
,表示凑齐金额0
不需要任何硬币。 - 对于每个金额
i
,遍历硬币的面额,计算凑齐金额i
所需的最少硬币数。 - 状态转移方程为:
dp[i] = min(dp[i], dp[i - coin] + 1)
,其中coin
为硬币的面额。 - 最终,
dp[amount]
即为凑齐总金额所需的最少硬币数。
复杂度分析
- 时间复杂度:
O(n * amount)
,其中n
是硬币的数量,amount
是目标金额。对于每个金额尝试使用每种硬币,因此在最坏情况下,可能对amount
种金额进行O(n)
次递归调用。 - 空间复杂度:
O(amount)
- 使用了一个长度为
amount + 1
的数组dp
; - 递归调用的深度在最坏情况下可能达到
amount
。
- 使用了一个长度为
代码
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
let dp = new Array(amount + 1).fill(-666);
const helper = (num) => {
if (num == 0) return 0;
if (num < 0) return -1;
if (dp[num] !== -666) return dp[num];
let res = Infinity;
for (let coin of coins) {
let sub = helper(num - coin);
if (sub == -1) continue;
res = Math.min(res, sub + 1);
}
dp[num] = res == Infinity ? -1 : res;
return dp[num];
};
return helper(amount);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
983 | 最低票价 | 数组 动态规划 | ||
2218 | 从栈中取出 K 个硬币的最大面值和 | 数组 动态规划 前缀和 | ||
2224 | 转化时间需要的最少操作数 | 贪心 字符串 | ||
2547 | 拆分数组的最小代价 | 数组 哈希表 动态规划 1+ | ||
2902 | 和带限制的子多重集合的数目 | 数组 哈希表 动态规划 1+ | ||
2915 | 和为目标值的最长子序列的长度 | 数组 动态规划 | ||
2952 | 需要添加的硬币的最小数量 | 贪心 数组 排序 | ||
2979 | 最贵的无法购买的商品 🔒 | 数学 动态规划 数论 |