代码随想录算法训练营day43

思路：首先了解完全背包的定义，即每个物品的数量可以有无限个，即可以全部只放一个物品，01背包问题每一个物品只能放一个。同样dp五部曲：dp数组，dp[j]表示背包重量为j时能装的最大价值；递推公式，当物品i可以先放进去时，dp[j]=max(dp[j],dp[j-weight[i]]+value[i])；初始化，一开始都初始化为0；遍历顺序，这里就是完全背包和01背包的区别，01背包为了避免重复放入元素，会从背包容量从大到小的遍历，而完全背包问题每个元素可以重复放入，故从小到大遍历，因为我们就是要让物品可以重复放入！；举例：三个物品，weight={1,3,4}，value={15,20,30}，背包容量4，dp数组，初始化{0,0,0,0,0}，物品0，{0,15,30,45,60}，物品1，{0,15,30,45,60}，物品2，{0,15,30,45,60}。时间复杂度O(mn)

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

本题有一个关键点，即遍历顺序，对于完全背包问题，使用一维数组，两个for循环先遍历物品后背包容量，和先背包容量后物品，都是可以的。因为dp[j]是根据j之前的dp[j]计算出来的，只要保证递推公式运行的时候之前的dp[j]已经被计算过即可。

思路：本题一个零钱可以无限使用，就是完全背包。背包重量为amount，物品weight为面值，value也为面值，需要保证背包恰好装满，求可以装满的方法数，故dp数组需要有所变化，回想目标和那题，但是不同之处是这里是组合数，而目标和那题是排列数！比如5=1+2+2和2+1+2是一种方法。dp五部曲：dp数组，dp[j]表示容量为j的背包装满用的方法数量（组合数）；递推公式，当物品i可以放入时，dp[j]+=dp[j-coins[i]]，这里就和之前比较类似了，所有求方法数基本都是这个递推公式；初始化，dp[0]一定初始化为1，即amount=0的组合数为1（一个钱都没有，也是一种方法），否则后面的所有递推都是0，然后是其他dp[j]初始化为0；遍历顺序，这里比较关键，普通的完全背包问题需要计算的是最大价值数，不管先遍历物品还是容量，最后算出来的答案都是一样的，但本题需要算的是组合方法数，如果先遍历物品后遍历容量，比如两个物品1和2，那么先放入的就是1，后放入的就是2，{1,2}，不会再算一遍{2,1}，故这样得到的答案就是正确的，如果先遍历容量后遍历物品，则每一个容量值，都计算了每一个物品的放入，包括{1,2}和{2,1}，这时算出来的是排列数，不符合要求；举例略。时间复杂度O(mn)。

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

思路：本题也是完全背包问题的思路，背包容量为target，weight和value都是nums中的元素，但是要求的是所有可能的组合数，不同顺序被视作不同的组合，故本题求的是排列数。需要注意，如果要求把所有结果列出，则只能使用回溯法暴搜，但本题只要求数量，故使用dp比较容易。dp五部曲：dp数组，dp[j]表示容量为j的背包装满的方法数量（排列数）；递推公式，如果物品i能先放进去，dp[j]+=dp[j-weight[i]]；初始化，dp[0]为1，其他为0；遍历顺序，这里比较关键，因为本题求的是排列数，和上题的组合数不同，需要把给定背包容量j下的所有情况都考虑一遍，故两个for循环先遍历容量后物品；举例略。时间复杂度O(mn)。

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

一开始提交出现runtime error，显示整数越界。看解答后发现需要保证答案在32位整数范围。
标答：

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for (int i = 0; i <= target; i++) { // 遍历背包for (int j = 0; j < nums.size(); j++) { // 遍历物品if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
};

思路：本题之前做过类似，但之前的题目一次只能爬一步或者两步，故递推公式比较简单，dp[i]=dp[i-1]+dp[i-2]，但本题可以一次爬m步，使用之前的思路就难以实现了。这里需要把这题对应到完全背包问题，总阶数n即为背包容量，有m个物品，重量和价值都为1-m，需要求装满的方法数，注意本题不同顺序是不同爬楼方法，故求的是排列数。dp五部曲：dp数组，dp[j]表示装满容量j的方法数（排列）；递推公式，dp[j]+=dp[j-weight[i]]；初始化，之前的那题没有考虑dp[0]，但这里是用的背包问题的思路，故需要将dp[0]初始化为1，其他为0；遍历顺序，由于是求排列，故先容量后物品；举例略。时间复杂度O(mn)。

#include<bits/stdc++.h>
using namespace std;int solve(int m,int n){vector<int> dp(n+1,0);dp[0]=1;//本题是从0开始初始化for(int j=1;j<=n;j++){for(int i=1;i<=m;i++){if(i<=j){dp[j]+=dp[j-i];}}}return dp[n];
}int main(){int m,n;while(cin >> n >> m){cout << solve(m,n) << endl;}return 0;
}