LeetCode 322. 零钱兑换

◎

本节目标

用完全背包状态求组成指定金额所需的最少硬币数。

返回背包模型框架

查看 LeetCode 原题

题意与约束

每种硬币可无限次使用，求组成 amount 的最少硬币数；不可组成时返回 -1。

第一反应与重复子问题

组成金额 x 的最后一枚硬币若为 coin，此前只需解决金额 x-coin；相同金额会由不同选择反复到达。

状态定义与转移推导

dp[x] 是组成 x 的最少硬币数。dp[0]=0，其他先设为大于任何可能答案的哨兵；枚举硬币后取 dp[x]=min(dp[x],dp[x-coin]+1)。

正确性依据

每个非零可行方案都有最后一枚硬币，枚举它覆盖全部方案；转移选择最少的前缀方案，归纳得到最优数量。

样例执行过程

[1,3,4] 组成 6 时，3+3 给出 2，比贪心先取 4 再取两个 1 更少。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int current = 1; current <= amount; current++) {
            for (int coin : coins) {
                if (coin <= current) {
                    dp[current] = min(dp[current], dp[current - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

Python

Python 3

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for current in range(1, amount + 1):
            for coin in coins:
                if coin <= current:
                    dp[current] = min(dp[current], dp[current - coin] + 1)
        return -1 if dp[amount] == amount + 1 else dp[amount]

复杂度分析

时间 O(amount·n)，空间 O(amount)。

边界与易错点

• amount=0 返回 0。
• 哨兵状态不能参与成正常答案。
• 不可达时转回 -1。

模式迁移

当每种选择可重复且目标是最小代价时，使用正序容量和无穷大初始化。