代码随想录算法训练营第三十二天 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、卡码网57. 爬楼梯
代码随想录算法训练营第三十二天任务
- 完全背包理论
- 卡码网52. 携带研究材料
- 518.零钱兑换II
- 377. 组合总和 Ⅳ
- 卡码网57. 爬楼梯
完全背包理论
有N件物品和⼀个最多能背重量为W的背包。第 i 件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放⼊背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
eg:
背包最大重量为4。
物品为：
每件商品都有无限个！
问背包能背的物品最大价值是多少？
- 确定dp数组的含义
dp[i][j] 表示背包容量为j的背包能背[0~i]中物品的最大价值。 - 确定递推公式。
不装当前物品 i ： dp[i][j] = dp[i - 1][j]
装当前物品 i : dp[i][i] = dp[i][j - weight[i]] + value[i]
因为每件商品有无限个，所以不是dp[i - 1][i - weight[i]], 而是dp[i][j - weight[i]]， 之前这个物品装入过，但因为有空间，还可以再装入。
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]) - 初始化
dp[i][0]: 背包容量为0，什么物品都装不下，所以为0。
因为dp[i][j] 由上方和左方推倒而来，所以dp[0][j] 需要初始化。
只要容量能装下物品0，就可劲装：
j > weight[0]: dp[0][j] = dp[0][j - weight[0]] + value[0]; - 确定遍历顺序
完全背包的物品是可以添加多次的，所以要从小到大去遍历// 先遍历物品，再遍历背包for(inti=0;i<weight.size();i++)// 遍历物品{for(intj=weight[i];j<=bagWeight;j++)// 遍历背包容量{dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);}}// 先遍历背包，再遍历物品for(intj=0;j<=bagWeight;j++)// 遍历背包容量{for(inti=0;i<weight.size();i++)// 遍历物品{if(j-weight[i]>=0)dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);}} - 举例推导dp数组
纯完全背包的面试题：要求先用二维dp数组实现，然后再用一维dp数组实现，最后在问，两个for循环的先后是否可以颠倒？为什么？
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。 377.组合总和IV
卡码网52. 携带研究材料
题目链接：卡码网52. 携带研究材料
#include<iostream>#include<vector>usingnamespacestd;intmain(){intitem,totalWeight;cin>>item>>totalWeight;vector<int>weight(item,0);vector<int>value(item,0);for(inti=0;i<item;++i){cin>>weight[i];cin>>value[i];}// dp[i][j] [0~i]类物品中装入容量为j的行李中的最大价值vector<vector<int>>dp(item,vector<int>(totalWeight+1,0));// 初始化第一行for(intj=weight[0];j<=totalWeight;++j){dp[0][j]=dp[0][j-weight[0]]+value[0];}for(inti=1;i<item;++i){// 物品for(intj=0;j<=totalWeight;++j){// 容量if(j<weight[i])dp[i][j]=dp[i-1][j];else{dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);}}}cout<<dp[item-1][totalWeight]<<endl;return0;}518.零钱兑换II
题目链接：518.零钱兑换II
这道题很契合完全背包问题。
coins数组相当于物品，amount相当于背包。
只不过这里的dp[i][j] 不表示价值，而是表示凑成这个amount有多少种方式。多少和494. 目标和有点相似。目标和是01背包问题，这道题是完全背包问题。
- 确定dp[i][j]的含义
dp[i][j] 表示 coins中下标为[0~i]的数凑成金额 j 的组合数。 - 确定递推公式
不包含当前下标为 i 的coin，dp[i][j] = dp[i - 1][j]
包含当前下标为 i 的coin, dp[i][j] = dp[i][j - coins[i]]
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] - 初始化
凑成金额为0的组合数相当于什么都不选，算一种方式，即dp[i][0] = 1;
当 j % coins[0] == 0, dp[0][j] = 1; - 遍历顺序
从小到大遍历 - 举例推到dp数组
classSolution{public:intchange(intamount,vector<int>&coins){// dp[i][j] 表示 coins中下标为[0~i]的数凑成金额 j 的组合数。intn=coins.size();vector<vector<uint64_t>>dp(n,vector<uint64_t>(amount+1,0));// 小面值硬币组合出大金额，组合方式爆炸式增长，可能超出64 位整数上限。// 初始化for(intj=0;j<=amount;++j){if(j%coins[0]==0)dp[0][j]=1;}for(inti=1;i<n;++i){dp[i][0]=1;for(intj=1;j<=amount;++j){if(j<coins[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];}}returndp[n-1][amount];}};377. 组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
这道题和518.零钱兑换II相似，不同之处在于这道题把顺序不同的序列视为不同的组合。
- 确定dp[i][j]的含义
dp[i][j] 表示 使用下标为 0~i 数字凑成总和为 j 的排列数量。 - 确定递推公式
不包含当前下标为 i 的num，dp[i][j] = dp[i - 1][j]
包含当前下标为 i 的coin, dp[i][j] = dp[n][j - nums[i]]
dp[i][j] = dp[i - 1][j] + dp[n][j - nums[i]]
为什么不是 dp[i][j - nums[i]]？
当使用 nums[i] 时，剩余和 j - nums[i] 的凑法必须允许再次使用所有数字，才能体现排列。
其中 n 是数组总长度，dp[n][…] 表示所有数字都可用的状态。 - 初始化
凑成为0的组合数相当于什么都不选，算一种方式，即dp[i][0] = 1; - 遍历顺序
从小到大遍历 - 举例推到dp数组
classSolution{public:intcombinationSum4(vector<int>&nums,inttarget){// dp[i][j] 表示 nums中下标为[0~i]的数组合成和为 target 的组合排列数。intn=nums.size();vector<vector<uint64_t>>dp(n+1,vector<uint64_t>(target+1,0));// 初始化for(inti=0;i<=n;++i){dp[i][0]=1;// 凑成 0 都有 1 种方法}for(intj=1;j<=target;++j){for(inti=1;i<=n;++i){if(j<nums[i-1])dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i-1][j]+dp[n][j-nums[i-1]];}}returndp[n][target];}};卡码网57. 爬楼梯
题目链接：卡码网57. 爬楼梯
思路同上题！
#include<iostream>#include<vector>usingnamespacestd;intmain(){intn,m;cin>>n>>m;// n 相当于 背包容量， 1 ~ m 相当于物品，可以重复装vector<vector<int>>dp(m+1,vector<int>(n+1,0));// 初始化for(inti=0;i<=m;++i){dp[i][0]=1;}for(intj=1;j<=n;++j){for(inti=1;i<=m;++i){if(j<i)dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i-1][j]+dp[m][j-i];}}cout<<dp[m][n]<<endl;return0;}