当前位置：首页 > news >正文

代码随想录算法训练营第四十二天|52. 携带研究材料、518. 零钱兑换 II、377. 组合总和 Ⅳ、57. 爬楼梯（进阶）

news 2026/5/12 18:23:35

52. 携带研究材料

思路：这是一个纯粹的完全背包问题，这里与01背包的区别就是一个物品可以无限次使用，所以内层循环的遍历顺序要变成正序遍历，还有此时一位dp数组的循环顺序先先物品再背包和先背包再物品都是可以的，因为可以重复选择。其他的和01背包问题都一样。

我的代码：

#include <iostream> #include <vector> using namespace std; int main() { int n,bagweight; cin>>n>>bagweight; vector<int> weight(n,0); vector<int> value(n,0); for(int i=0;i<n;i++) { int x,y; cin>>x>>y; weight[i]=x; value[i]=y; } vector<int> dp(bagweight+1,0); for(int i=0;i<n;i++) { for(int j=weight[i];j<=bagweight;j++) { dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); } } cout<<dp[bagweight]<<endl; return 0; }

518. 零钱兑换 II

思路：这道题目和之前的求总和很像，重点是这道题目选取的顺序是无关的，这里要注意遍历顺序此时会影响到是排列数还是组合数，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。要理解这个需要自己去打印dp数组才能有感觉，可以借助ai生成一个。dp[j] += dp[j - nums[i]]。注意C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。

我的代码：

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++) { if(dp[j]<INT_MAX-dp[j-coins[i]]) { dp[j]+=dp[j-coins[i]]; } } } return dp[amount]; } };

377. 组合总和 Ⅳ

思路：这题和上一道题目很像，重点是这里是排列而不是组合，所以需要先遍历背包再遍历物品，那么这里再循环内的语句需要注意不要引发数组访问错误，
if(j-nums[i]>=0&&dp[j]<=INT_MAX-dp[j-nums[i]]) { dp[j]+=dp[j-nums[i]]; }
if语句不要漏了，同属注意整数溢出问题。换一个遍历顺序和上一题就一样了。
注意，dp数组一定一定要初始化，我已经犯了好几次这个错误了，属于是总想着套模板，没有按照动规五部曲去一步一步想。

我的代码：

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]>=0&&dp[j]<=INT_MAX-dp[j-nums[i]]) { dp[j]+=dp[j-nums[i]]; } } } return dp[target]; } };

57. 爬楼梯（进阶）

思路：之前做过这道题目，在回溯的时候，这里其实把可以上的台阶数扩大到1-m就可以变成一个完全背包问题，转换之后这道题目也和前面几道题目一样了，注意这里也是排列而不是组合。

我的代码：

#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=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(i-j>=0) dp[i]+=dp[i-j]; } } cout<<dp[n]<<endl; } }