算法 - 零钱兑换 (Coin Change)

Posted on

1. 题目

给你一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额。计算凑成总金额所需的最少的硬币个数。每种硬币可以无限使用。如果无法凑出，返回 -1。

示例:

1
2
3
4
5
6
7
8
输入: coins = [1, 2, 5], amount = 11
输出: 3  （11 = 5 + 5 + 1）

输入: coins = [2], amount = 3
输出: -1 （凑不出）

输入: coins = [1], amount = 0
输出: 0

2. 解题思路

这是完全背包求最少数量的经典题。贪心（每次取最大面额）在这里不成立（如 coins=[1,3,4], amount=6 贪心得 4+1+1=3 枚，最优是 3+3=2 枚），必须用 DP。

定义 dp[i] = 凑出金额 i 所需的最少硬币数。

转移：对于金额 i，枚举最后一枚用的硬币 c（c <= i），则

1
dp[i] = min(dp[i - c]) + 1

初始化：

  • dp[0] = 0（凑 0 需要 0 枚）。
  • 其余 dp[i] = amount + 1（当作正无穷，因为最多也不会超过 amount 枚），或 Infinity。

最后若 dp[amount] > amount 说明没被更新过，返回 -1。

  • 时间复杂度：O(amount × coins数)。
  • 空间复杂度：O(amount)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function coinChange(coins: number[], amount: number): number {
    const dp = new Array(amount + 1).fill(amount + 1); // 视作 +∞
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const c of coins) {
            if (c <= i) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }

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

console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([2], 3));        // -1
console.log(coinChange([1, 3, 4], 6));  // 2

4. 面试延伸

  • 零钱兑换 II（518，凑法总数）：把 min+1 换成 dp[i] += dp[i-c]，且外层遍历硬币、内层遍历金额以保证组合不计顺序，是完全背包计数的标准写法。
  • 完全背包 vs 0-1 背包：内层金额遍历方向决定「可重复用」——完全背包正序（能用多次），0-1 背包逆序（每枚只用一次）。这是背包问题的核心分水岭。
  • 要输出具体用了哪些硬币：额外记录 choice[i] 前驱，最后回溯。
  • 常见坑：求「最少」用 min，求「方法数」用「加法」；初始化 dp[0] 的含义要和题目对齐。
  • 若问「为什么不用贪心」，一定要举 [1,3,4] 凑 6 的反例，这是本题最重要的理解点。

难度：中等 | LeetCode 322 题 | 完全背包基石