LeetCode 322. 零钱兑换

约 5 分钟
文章信息 25 个分类 7 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 历史考题 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 网易 旷视 亚马逊 虾皮 哔哩哔哩 LeetCode 热题 100 面试经典 150 题
标签
数组 动态规划 广度优先搜索 背包问题 完全背包问题 完全背包 零钱兑换问题
目录

题目描述

✅ 322. 零钱兑换

image-20250419053630089

题意分析

给定若干种硬币面额和一个目标金额，每种硬币的数量不限，问凑出目标金额最少需要多少枚硬币；凑不出就返回 -1。

先厘清问的是什么：要的是枚数的最小值，不是方案数，也不是具体用了哪些硬币。这一点决定了状态里存的是一个最小值，聚合方式是取 min 而不是求和。

「每种硬币数量不限」是最重要的信号。它意味着同一种面额可以在答案里重复出现，「每种硬币用或不用」这样的两选一框架装不下它；同时它还带来一个好性质——凑出金额 x 的最省方案里，去掉任意一枚硬币后剩下的部分，一定也是凑出「x 减那枚面额」时最省的凑法之一，也就是说小金额的答案可以放心地被大金额复用。

「面额是任意给定的正整数」则排除了贪心。如果面额构成的体系不满足特殊性质，「每次尽量拿大额」并不最优：面额 [1,3,4] 凑 6 时贪心会拿 4+1+1 共 3 枚，而 3+3 只要 2 枚。所以必须真的把所有决策枚举完。

需要留意的边界情形：目标金额为 0 时答案是 0，一枚也不用；某些面额可能比目标金额还大，这些硬币压根用不上，索引时不能算出负数；确实凑不出时（如面额只有 2 而目标是 3）要返回 -1，所以算法内部必须能区分「凑不出」和「凑出来了但枚数很多」这两件事。

解法：完全背包动态规划

核心思路

用 dp[money] 表示凑出金额 money 所需的最少硬币数。初始时只有 dp[0] = 0，其余位置设为不可达；枚举每种硬币并正序更新金额，使同一种硬币可以重复使用。

转移方程为 dp[money] = min(dp[money], dp[money - coin] + 1)。不可达值取 amount + 1，既大于所有可能答案，又不会在加一时溢出。

解题步骤

  • 创建长度为 amount + 1 的 dp，全部填为 amount + 1，再令 dp[0] = 0。
  • 依次枚举硬币 coin，金额从 coin 正序遍历到 amount。
  • 用 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
}

复杂度分析

  • 时间复杂度：$O(nS)$，n 为硬币种数，S 为目标金额。
  • 空间复杂度：$O(S)$，使用一个一维状态数组。

关键点总结

  • dp[money] 表示最少硬币数，转移时枚举最后使用的硬币。
  • 金额正序遍历，才能在同一轮重复使用当前硬币。
  • amount + 1 是安全的不可达标记，最终要转换为 -1。

易错点总结

  • 忘记设置 dp[0] = 0，所有状态都会保持不可达。
  • 金额倒序遍历会变成每种硬币最多使用一次。
  • 用整数最大值作哨兵后直接加一，会发生溢出。
  • 无解时应返回 -1，不能直接返回哨兵值。

相似题目

题目 难度 考察点
LCR 103. 零钱兑换 中等 与本题同题异名，代码可直接照搬
面试题 08.11. 硬币 中等 面额固定为 1/5/10/25 但求方案数，聚合从 min 换成累加并需要取模
518. 零钱兑换 II 中等 求组合数，两层循环顺序不再自由，面额必须在外层否则会重复计数
377. 组合总和 Ⅳ 中等 求排列数，顺序不同算不同方案，两层循环顺序与 518 正好相反
LCR 104. 组合总和 Ⅳ 中等 与 377 同题异名，适合与 518 放在一起对照「组合 vs 排列」的循环顺序
279. 完全平方数 中等 面额不是给定的而是自行枚举出的平方数，且保证有解（1 是平方数），无需 -1
139. 单词拆分 中等 状态变成布尔可达性，物品是变长单词，转移要额外比较子串是否匹配
1155. 掷骰子等于目标和的方法数 中等 骰子个数固定，必须多一维记录已用个数，属于「恰好用 k 件」的分组背包
1449. 数位成本和为目标值的最大数字 困难 要求成本恰好等于目标且最大化位数后还要拼出最大数字，需回溯还原方案
416. 分割等和子集 中等 每个数只能用一次，是 01 背包，内层金额必须倒序，正好与本题形成对照