代码随想录算法训练营第43天 [完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ 70. 爬楼梯]

代码随想录算法训练营第43天 [完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ 70. 爬楼梯]

---

一、完全背包

链接: 代码随想录.
思路：完全背包模板
做题状态：看解析后做出来了

#include<iostream>
#include<vector>
using namespace std;void test_CompletePack(vector<int> weight, vector<int> value, int V ){vector<int> dp(V+1,0);//物品在外层，背包在内层for(int i = 0;i<weight.size();i++){//遍历背包的时候正向遍历for(int j = weight[i];j<=V;j++){dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);}}cout << dp[V] <<endl;
}int main(){int N;int V;vector<int> weight;vector<int> value;cin >> N >> V;while(N--){int w;int v;cin >> w >> v;weight.push_back(w);value.push_back(v);}test_CompletePack(weight, value, V);return 0;
}

二、518. 零钱兑换 II

链接: 代码随想录.
思路：完全背包应用 求多少种的递推公式时 dp[j] += dp[j - weight[i]],初始化dp[0] = 1
做题状态：看解析后做出来了

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1,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];}
};

三、377. 组合总和 Ⅳ

链接: 代码随想录.
思路：完全背包应用，求多少种的递推公式时 dp[j] += dp[j - weight[i]],初始化dp[0] = 1
做题状态：看解析后做出来了

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1,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];}
};

四、70. 爬楼梯

链接: 代码随想录.
思路：完全背包应用
做题状态：看解析后做出来了

#include<iostream>
#include<vector>
using namespace std;int main(){int n;int m;while(cin >> n >> m){vector<int> a(n+1);a[0] = 1;for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){if(i >= j){a[i] += a[i-j];}}}cout << a[n] <<endl;}return 0;
}