算法训练营第44天|完全背包 LeetCode 518.零钱兑换Ⅱ 337.组合总和Ⅱ

完全背包

题目链接：

完全背包

代码：

#include<iostream>
#include<vector>
using namespace std;

void test(vector<int>weight,vector<int>value,int bagweight){
    vector<int>dp(bagweight+1,0);
    for(int i=0;i<weight.size();i++){
        for(int j=0;j<=bagweight;j++){
            if(j>=weight[i])
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<<dp[bagweight]<<endl;
}
int main(){
    int N,V;
    cin>>N>>V;
    vector<int>weight;
    vector<int>value;
    for(int i=0;i<N;i++){
        int w;
        int v;
        cin>>w>>v;
        weight.push_back(w);
        value.push_back(v);
    }
    test(weight,value,V);
    return 0;
}

LeetCode 518.零钱兑换Ⅱ

题目链接：

LeetCode 518.零钱兑换Ⅱ

代码：

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];
    }
};

LeetCode 337.组合总和Ⅱ

题目链接：

LeetCode 337.组合总和Ⅱ

代码：

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