LeetCode LCR 103. 零钱兑换

约 4 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 动态规划 广度优先搜索 LCR

题目描述

✅ LCR 103. 零钱兑换

image-20260929004419419

image-20260929004419420

题意分析

每种正面额硬币可以使用任意多枚，求恰好凑出 amount 所需的最少枚数；无法凑出时返回 -1。金额为 0 时，不取硬币就是最优方案，答案为 0。

总金额不超过 $10^4$，适合按金额保存最优结果。面额可以远大于总金额，这些硬币直接跳过即可。

解法：完全背包求最少硬币

核心思路

[!blue]

定义 dp[j] 为仅使用已经处理过的面额、恰好凑出金额 j 所需的最少硬币数。初始 dp[0] = 0，其余金额不可达。所有面额都至少为 1，所以任何凑出 j 的方案最多用 j 枚硬币；用 amount + 1 表示不可达，一定大于所有合法答案，不要求输入中实际存在面额 1。

处理面额 coin 时，最优方案要么不使用它，保留原来的 dp[j]；要么至少使用一枚，去掉其中一枚后剩余金额为 j - coin，候选枚数就是 dp[j - coin] + 1。因此执行 dp[j] = min(dp[j], dp[j - coin] + 1)。

剩余部分仍允许使用 coin，所以内层金额必须从小到大。更新 j 时，较小的 j - coin 已完成本轮处理，能够包含任意多枚当前面额；再加一枚即可覆盖所有使用它的方案。每种面额处理结束后，整张表就保存了允许这些面额时的最优结果。

金额循环从 coin 开始，保证 j - coin 非负。若面额超过 amount，循环不会执行，也不会访问越界下标。若前驱不可达，候选值为 amount + 2，比当前最多为 amount + 1 的状态更差，取最小值时不会误选它。

最后若 dp[amount] > amount，该金额仍不可达，返回 -1；否则返回最少枚数。amount = 0 时没有任何转移，初值 0 就是答案。

解题步骤

  1. 创建长度为 amount + 1 的数组，将正金额初始化为不可达，保留 dp[0] = 0。
  2. 逐个处理硬币面额 coin。
  3. 从 coin 到 amount 正序更新，比较旧答案与补上一枚硬币的候选答案。
  4. 根据目标状态是否仍不可达，返回 -1 或最少枚数。

代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        // amount + 1 严格大于任何合法答案，充当「不可达」哨兵且不会溢出。
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            // 正序遍历，dp[j - coin] 已包含本面额，允许同一面额取多枚。
            for (int j = coin; j <= amount; ++j) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    // amount + 1 严格大于任何合法答案，充当「不可达」哨兵且不会溢出。
    for i := 1; i <= amount; i++ {
        dp[i] = amount + 1
    }

    for _, coin := range coins {
        // 正序遍历，dp[j-coin] 已包含本面额，允许同一面额取多枚。
        for j := coin; j <= amount; j++ {
            dp[j] = min(dp[j], dp[j-coin]+1)
        }
    }

    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

复杂度分析

  • 时间复杂度：$O(n(A+1))$，其中 $n$ 为面额数、$A$ 为总金额，包含金额为 0 时的面额遍历。
  • 空间复杂度：$O(A+1)$，只保存一维金额状态。

关键点总结

[!green]

  • 正序读取的是已经允许当前面额的状态，因此可以重复取用；这里与每个位置只能选择一次的背包不同。
  • 不可达哨兵应大于真实答案上界，并能安全地参与加一。
  • 求最少枚数时取最小值，不累计硬币排列或组合的数量。

易错点总结

[!yellow]

  • 将所有状态初始化为 0，会把无法凑出的正金额误认为不需要硬币。
  • 容量倒序会限制当前面额只能用一次。
  • 用最大整数作哨兵后直接加一，可能发生溢出；本实现使用 amount + 1。
  • 总是先拿最大面额不能保证最少枚数，必须保留所有已处理面额带来的最优结果。

相似题目

题目 难度 关联与区别
518. 零钱兑换 II 中等 候选面额可重复使用，本题最小化硬币数量，原题累计不区分顺序的组合数。
279. 完全平方数 中等 把可选面额限制为完全平方数后，同样求凑成目标所需的最少项数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/17539201
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！