💴518.零钱兑换II

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

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

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

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

思路

基本思想

典型的完全背包问题，并且求解的是恰能装满背包的方案数，而不是最大价值

所以有两点需要注意：

• 背包容量从小到大遍历，先更新小容量，大容量依赖于小容量，从而物品可以被放入任意次

• 递推方程不一样，采用累加的方式 $$ dp[j]+=d[j-weight[i]] $$ 代表加入不同的物品，背包的容量有不同的变化，从而有不同的方案，最终将所有的方案累加

执行流程

1. 初始化dp数组，注意dp[0]=1,代表总金额为0有一种方案就是什么都不加
2. 按照完全背包的方式遍历
3. 按照递推方程更新dp数组
4. 返回最终结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        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]];
            }
        }
        return dp[amount];
    }
};

总结

有三点需要注意：

• 完全背包容量的遍历顺序从小到大，这样大容量才能依赖小容量，也就是物品可以重复加入
• 求解的是恰能装满背包的所有方案数，而不是最大价值，所以需要累加所有可能的方案
• dp[0]=1，代表总金额为0时方案数为1，什么都不加