518. 零钱兑换 II-LeetCode

关键字：完全背包、组合数问题

dp[0][0] 即价值0的物品放到容量为0的背包，应该也算一种方案 本题考查组合问题：问题求解为组合数，即dp[i][j] = dp[i-1][j] + dp[i][j - nums[i]] 个方案

public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n+1, vector<int>(amount+1,0));
        //1.边界初始化
        dp[0][0] = 1;
        //2 dp主过程
        for(int i=1;i<=n;i++) {
            for(int j=0;j<=amount;j++) {
                if(coins[i-1] <= j) {
                    dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][amount];
    }
};