518. 零钱兑换 II

518. 零钱兑换 II

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

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

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

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

示例 1：

输入：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：

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

示例 3：

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

提示：

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

---

解题思路

状态表示

​ 这道题比 322. 零钱兑换 还简单！很明显这就是一个完全背包问题，其中硬币就是物品，硬币的金额就是体积，背包体积就是总金额！

​ 所以根据 “经验 + 题目要求”，可以得到 dp[i][j] 表示在前 i 个硬币中选，总金额正好等于 j，此时一共有多少种硬币组合。

状态转移方程

初始化

​ 因为题目说如果任何硬币组合都无法凑出总金额，返回 0，所以只需要将第一行初始化为 0 即可，而这个步骤我们直接通过创建 dp 表的时候进行初始化即可。

​ 但是因为第一个元素表示的是没有硬币可以选，但是背包空间为 0，相当于可以满足背包空间了，所以是一种硬币组合，所以 dp[0][0] 初始化为 1。

遍历顺序

​ 从上往下，从左往右遍历。

返回值

​ 根据状态表示，返回的就是最后一个位置 dp[n][amount]。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 创建dp表，dp[i][j]表示在前i个硬币中选，总金额正好等于j，此时的硬币组合数
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));

        // 初始化
        dp[0][0] = 1;

        // 从上往下，从左往右遍历
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 0; j <= amount; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1])
                    dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
};

优化

所有的「背包问题」，都可以进行空间上的优化。

对于 完全背包 类型的，我们的优化策略是：

• 删掉第一维

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 创建dp表
        int n = coins.size();
        vector<int> dp(amount + 1);

        // 初始化
        dp[0] = 1;

        // 从上往下，从左往右遍历
        for(int i = 1; i <= n; ++i)
            for(int j = coins[i - 1]; j <= amount; ++j)
                dp[j] += dp[j - coins[i - 1]];

        return dp[amount];
    }
};