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;
}
}
今日总结
今天的题目在有01背包的基础上还是比较好做的，注意一下遍历顺序的变化，还有注意整数溢出的问题。理解排列数和组合数的遍历顺序上的区别。继续加油！
