leetcode.518.零钱兑换

class Solution {
public:
//求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];
// 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
// 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
//此题求得是组合数
    int change(int amount, vector<int>& coins) {
        vector<int> dp(10010,0);
dp[0]=1;//装满0 又一种方法，就是一个也不装
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                if (dp[j] < INT_MAX - dp[j - coins[i]]) { //防止相加数据超int
                    dp[j] += dp[j - coins[i]];
                }
            }
        }

return dp[amount];

        
    }
};

leetcode.377.组合总和Ⅳ

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(100100,0);
        dp[0]=1;
        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.size();i++){
                if(j>=nums[i]&&dp[j]<INT_MAX-dp[j-nums[i]])
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];
    }
};