518. 零钱兑换 II

第一道完全背包的题目，抄了随想录

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // dp[j]：凑成总金额j的货币组合数为dp[j]
        vector<int>dp(amount+1);
        dp[0]=1;
        // dp[j] += dp[j - coins[i]];
        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];
    }
};