518. 零钱兑换 II

Problem: 518. 零钱兑换 II

思路

纯纯的背:

求装满背包的方法 dp[j] += dp[j - nums[i]]。

注意遍历背包和遍历物品的顺序。

有下面两种：

排列问题：先背包再物品，注意内层循环判断背包大于物品

组合问题：先物品再背包，注意遍历背包要是否要倒序就涉及到是01背包还是完全背包。

本题是组合问题且是**完全背包(顺序背包)**。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

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