LeetCode 322. 零钱兑换
题目描述
题意分析
给定若干种正整数面额
coins，每种硬币都有无限枚。要求恰好凑出金额amount，并让使用的硬币总数最少；无法凑出时返回-1。求的是最少枚数，不是凑钱方案数，也不要求输出具体用了哪些硬币。目标金额为
0时不需要任何硬币，答案是0。面额没有特殊规律，因此不能假设每次优先使用最大面额就能得到最优解。
解法：完全背包动态规划
核心思路
[!blue]
对于一个金额，如果决定再放入一枚面额为
coin的硬币，就只需凑出剩余金额money - coin。因此可以保存每个较小金额的最优答案，再逐步计算更大金额，避免反复枚举完整的硬币组合。用
dp[money]表示使用目前已经处理过的面额，恰好凑出money所需的最少硬币数。初始还没有可用面额，只有dp[0] = 0；其他金额都设为不可达。每加入一种面额coin，需要在两种选择之间取最小值：
- 不使用当前面额，保留原来的
dp[money]。- 至少使用一枚当前硬币，先凑出
money - coin，再加一枚，候选值为dp[money - coin] + 1。因此转移为
dp[money] = min(dp[money], dp[money - coin] + 1)。任何使用当前面额的最优方案都能拆去一枚coin；剩余部分如果还能用更少硬币凑出，原方案就不是最优，所以这个转移不会遗漏更好的答案。金额必须从
coin向amount正序遍历。由于面额为正，money - coin更小，读取时已经允许使用本轮的硬币；在它的基础上再加一枚，就实现了同一种面额的无限次使用。如果倒序更新，读到的仍是本轮更新前的状态，就会把当前硬币限制为最多使用一次。不可达标记取
amount + 1：每枚硬币至少值1，任何可行方案都不会用超过amount枚硬币。对不可达状态再加一仍大于标记，不会把另一个不可达状态更新成可达；题目金额上限为10^4，加一也不会溢出。所有面额处理完后，dp[amount]就是答案，仍为标记则无解。
解题步骤
- 创建长度为
amount + 1的dp，设dp[0] = 0，其余位置为amount + 1。- 依次枚举硬币面额
coin。若它大于目标金额，本轮金额循环自然跳过。- 从
coin到amount正序枚举money，用dp[money - coin] + 1更新dp[money]的最小值。- 若
dp[amount]仍为不可达标记，返回-1；否则返回最少硬币数。
代码实现
class Solution {
public int coinChange(int[] coins, int amount) {
// 大于所有可能的硬币数，同时给加一留出安全空间。
int unreachable = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, unreachable);
// 空金额不需要硬币，是其他可达状态的递推起点。
dp[0] = 0;
for (int coin : coins) {
// 金额正序读取本轮已更新状态，允许当前硬币重复使用。
for (int money = coin; money <= amount; money++) {
dp[money] = Math.min(dp[money], dp[money - coin] + 1);
}
}
return dp[amount] == unreachable ? -1 : dp[amount];
}
}
func coinChange(coins []int, amount int) int {
// 大于所有可能的硬币数，同时给加一留出安全空间。
unreachable := amount + 1
dp := make([]int, amount+1)
// 只把正金额设为不可达，金额零保留默认零作为递推起点。
for i := 1; i <= amount; i++ {
dp[i] = unreachable
}
for _, coin := range coins {
// 金额正序读取本轮已更新状态，允许当前硬币重复使用。
for money := coin; money <= amount; money++ {
candidate := dp[money-coin] + 1
if candidate < dp[money] {
dp[money] = candidate
}
}
}
if dp[amount] != unreachable {
return dp[amount]
}
return -1
}
复杂度分析
设硬币种数为 $n$，目标金额为 $S$。
- 时间复杂度：$O(n(S+1))$。初始化需要 $O(S+1)$，每种面额最多更新 $S$ 个金额；写成 $S+1$ 也包含目标为零时对面额的遍历。
- 空间复杂度：$O(S+1)$，状态数组保存从 $0$ 到 $S$ 的答案。
关键点总结
[!green]
- 每加入一种面额，都比较“不用它”和“在较小金额上再用一枚”的最少枚数。
- 正序更新让本轮结果继续参与后续转移，对应每种硬币无限使用。
dp[0]是所有可达状态的起点，不可达标记要大于任何合法答案。
易错点总结
[!yellow]
- 正金额不能初始化为
0，否则会把尚未凑出的金额当成无需硬币就能到达；dp[0]也不能设为不可达。- 金额倒序遍历会把完全背包改成每种硬币最多使用一次，改变题意。
- 面额没有贪心所需的特殊性质，优先用大硬币不保证剩余金额可达或总枚数最少。
- 直接用整数最大值表示不可达，再执行
+ 1，可能溢出为负数并被误选为最优值。- 无解必须把内部的不可达标记转换为
-1，金额为零则应返回0。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 518. 零钱兑换 II | 中等 | 候选面额可重复使用，本题最小化硬币数量，原题累计不区分顺序的组合数。 |
| 279. 完全平方数 | 中等 | 把可选面额限制为完全平方数后，同样求凑成目标所需的最少项数。 |
| 377. 组合总和 Ⅳ | 中等 | 按金额或目标长度累积可重复选择的结果；本题求最少硬币数，该题先枚举目标以统计有序方案。 |