跳转至

518. 零钱兑换 II

力扣链接(中等)：https://leetcode.cn/problems/coin-change-ii

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

Text Only
1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

Text Only
1
2
3
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

Text Only
1
2
输入：amount = 10, coins = [10] 
输出：1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

个人题解

建议完成 494. 目标和 和 416. 分割等和子集 后再完成本题。

完全背包问题

由题“每一种面额的硬币有无限个”，考虑转换为完全背包问题。

动态规划（滚动数组）

  1. dp[j] 代表凑成总金额为 j 的硬币有 dp[j] 种组合；
  2. 组合类问题的 dp 递推公式：dp[j] += dp[j - coins[i]]；
  3. 初始化 dp[0] = 1；
  4. 组合问题外层 for 遍历物品，内层 for 遍历背包容量；排列问题外层 for 遍历背包容量，内层 for 遍历物品。完全背包内层 for 循环应该从前向后遍历；
  5. 手动推导 dp 无误。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 防止 coins 足够多时 dp[j] 越界
        typedef unsigned int uint;

        const int N = 5000 + 10;
        uint dp[N] = {};

        dp[0] = 1;

        for(int i = 0; i < coins.size(); i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }

        // debug 遍历顺序对 dp 数组的影响

        // for(int i = 0; i < coins.size(); i++) {
        //     for(int j = 0; j <= amount; j++) {
        //         if(j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
        //         cout << dp[j] << ' ';
        //     }
        //     cout << endl;
        // }

        // for(int j = 0; j <= amount; j++) {
        //     for(int i = 0; i < coins.size(); i++) {
        //         if(j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
        //         cout << dp[j] << ' ';
        //     }
        //     cout << endl;
        // }

        return dp[amount];
    }
};