【c++刷题笔记-动态规划】day37：完全背包理论基础、518.零钱兑换II、377. 组合总和 Ⅳ、卡码网：57. 爬楼梯

52. 携带研究材料（第七期模拟笔试） (kamacoder.com)

思路：完全背包，先遍历背包再遍历物品。从前向后遍历取最大值

重点：j>weight[i]才能满足装进背包的条件

#include<bits/stdc++.h>
using namespace std;
void fun(vector<int>& weight,vector<int>& value,int n){
    vector<int>dp(n+1,0);
    for(int j=0;j<=n;j++){
        for(int i=0;i<weight.size();i++){
            if(j-weight[i]>=0){
                dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
    }
    cout<<dp[n];
}
int main(){
    int N,V;
    cin>>N>>V;
    std::vector<int>weight;
    vector<int>value;
    for(int i=0;i<N;i++){
        int w,v;
        cin>>w>>v;
        weight.push_back(w);
        value.push_back(v);
    }
    fun(weight,value,V);
    return 0;
}

518. 零钱兑换 II - 力扣（LeetCode）

思路：完全背包，求组合数，先遍历物品再遍历背包

重点：dp[j]+=dp[j-coins[i]];求个数

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<int>dp(amount+1,0);
        dp[0]=1;
        for(int i=0;i<n;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ - 力扣（LeetCode）

思路：完全背包，求排列数，先遍历背包再遍历物品

重点：dp[j]+=dp[j-nums[i]];

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

57. 爬楼梯（第八期模拟笔试） (kamacoder.com)

思路：完全背包，求排列数，先遍历背包再遍历物品

重点：dp[i] += dp[i - j];

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    std::vector<int>dp(n+1,0);
    dp[0]=1;
    for (int i = 1; i <= n; i++) { // 遍历背包
        for (int j = 1; j <= m; j++) { // 遍历物品
            if (i - j >= 0) dp[i] += dp[i - j];
        }
    }
    cout<<dp[n];
    return 0;
}

总结

完全背包，先遍历物品再遍历背包是求组合数，先遍历背包再遍历物品是求排列数。

求组合的个数使用dp[j]+=dp[j-nums[i]];