代码随想录训练营Day43

本文主要是介绍代码随想录训练营Day43，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、完全背包
二、零钱兑换2
三、爬楼梯进阶版

前言

提示：这里可以添加本文要记录的大概内容：

今天是跟着代码随想录刷题的第43天，主要学了完全背包，零钱兑换2，爬楼梯进阶版

提示：以下是本篇文章正文内容，下面案例可供参考

一、完全背包

思路：和0-1背包不太一样的地方就是，他是从本层的减去这个重量对应的最高价值然后加上自己的价值来求的结果，而不是上一层，因为本层的减去这个重量的值的最高价值本身就有可能已经有这个值进去了，这里再用就有可能会多次利用，这正是题目想要的完全背包。

#include <iostream>
#include <vector>
using namespace std;void wcy(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=1;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);}wcy(weight,value,V);return 0;
}

二、零钱兑换2

思路：就是完全背包的思路，只不过j=coins【i】是因为要保证j-coins【i】有意义。

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]+dp[j-coins[i]];}}return dp[amount];}
};

三、爬楼梯进阶版

思路：直接带入上面表格，有多少种方法装满背包，排列，完全背包

#include <iostream>
#include <vector>
using namespace std;
int main() {int n, m;while (cin >> n >> m) {vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 0; i <= n; i++) { // 遍历背包for (int j = 1; j <= m&&j<=i; j++) { // 遍历物品dp[i] += dp[i - j];}}cout << dp[n] << endl;}
}