LeetCode 518. 零钱兑换 II

◎

本节目标

用硬币外层、金额正序的一维动态规划计算组合数。

返回背包模型框架

查看 LeetCode 原题

题意与约束

每种硬币可重复使用，计算组成 amount 的组合数；硬币顺序不同不产生新组合。

第一反应与重复子问题

每种面额可以取多枚，若同时枚举排列会重复。固定“处理到第几种硬币”即可让每个组合只有一种生成顺序。

状态定义与转移推导

dp[x] 是已处理硬币组成 x 的组合数。dp[0]=1；硬币在外层、金额从小到大更新 dp[x]+=dp[x-coin]。

正确性依据

本轮只在旧组合后追加当前面额，所有硬币索引非递减，故同一组合不因排列重复；正序允许当前硬币多次出现。

样例执行过程

金额 5、硬币 [1,2,5] 得到 4 组：五个 1、三个 1 加 2、一个 1 加两个 2、一个 5。

代码实现

C++

C++17

#include <vector>
using namespace std;

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

Python

Python 3

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

复杂度分析

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

边界与易错点

• 金额 0 只有空集合这一种组合。
• 金额外层会把 [1,2] 与 [2,1] 重复计数。
• 正序是“硬币可重复”的必要语义。

模式迁移

区分“最少数量”和“方案数”：公式相似，但状态值、聚合运算与初始化不同。