52. 携带研究材料思路这是一个纯粹的完全背包问题这里与01背包的区别就是一个物品可以无限次使用所以内层循环的遍历顺序要变成正序遍历还有此时一位dp数组的循环顺序先先物品再背包和先背包再物品都是可以的因为可以重复选择。其他的和01背包问题都一样。我的代码#include iostream #include vector using namespace std; int main() { int n,bagweight; cinnbagweight; vectorint weight(n,0); vectorint value(n,0); for(int i0;in;i) { int x,y; cinxy; weight[i]x; value[i]y; } vectorint dp(bagweight1,0); for(int i0;in;i) { for(int jweight[i];jbagweight;j) { dp[j]max(dp[j],dp[j-weight[i]]value[i]); } } coutdp[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, vectorint coins) { vectorint dp(amount1,0); dp[0]1; for(int i0;icoins.size();i) { for(int jcoins[i];jamount;j) { if(dp[j]INT_MAX-dp[j-coins[i]]) { dp[j]dp[j-coins[i]]; } } } return dp[amount]; } };377. 组合总和 Ⅳ思路这题和上一道题目很像重点是这里是排列而不是组合所以需要先遍历背包再遍历物品那么这里再循环内的语句需要注意不要引发数组访问错误if(j-nums[i]0dp[j]INT_MAX-dp[j-nums[i]]) { dp[j]dp[j-nums[i]]; }if语句不要漏了同属注意整数溢出问题。换一个遍历顺序和上一题就一样了。注意dp数组一定一定要初始化我已经犯了好几次这个错误了属于是总想着套模板没有按照动规五部曲去一步一步想。我的代码class Solution { public: int combinationSum4(vectorint nums, int target) { vectorint dp(target1,0); dp[0]1; for(int j0;jtarget;j) { for(int i0;inums.size();i) { if(j-nums[i]0dp[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(cinnm) { vectorint dp(n1,0); dp[0]1; for(int i1;in;i) { for(int j1;jm;j) { if(i-j0) dp[i]dp[i-j]; } } coutdp[n]endl; } }今日总结今天的题目在有01背包的基础上还是比较好做的注意一下遍历顺序的变化还有注意整数溢出的问题。理解排列数和组合数的遍历顺序上的区别。继续加油