完全背包理论基础
-
每个物品可以使用无数次
-
和01背包的区别：
-
1.因为每个物品可以使用无限次，所以要将遍历背包的顺序改成正序遍历
-
2.完全背包中，先遍历背包还是先遍历物品都可以
-
【注意】前提条件是纯完全背包问题
-
-
LeetCode 518 零钱兑换II
题目链接：518. 零钱兑换 II - 力扣（LeetCode）
【解题思路】
-
1.确定dp数组以及下标含义
-
dp[j]的定义是：装满容量为j的背包有dp[j]种方法
-
本题最终要求的是dp[amount]
-
-
2.确定递推公式
-
dp[j]+=dp[j-coins[i]]
-
-
3.确定dp数组如何初始化
-
dp[0]=1
-
因为要做累加，所以不能初始化为0
-
-
非0下标初始为0
-
-
4.确定遍历顺序
-
先遍历物品：
-
再遍历背包：
-
递推公式
-
-
-
Carl说先遍历物品是组合数，先遍历背包是排列数、对于这点，我的理解是：
-
先遍历物品后遍历背包：
-
1）外层固定物品1，进入内层循环
-
2）背包容量不断增加
-
物品1被重复添加进不同容量的背包中，直到背包容量遍历完毕
-
-
3）背包容量遍历完毕后，执行下一次循环，开始添加物品2
-
物品1已经被添加进每一个不同容量的背包里，因此物品2肯定会在物品1之后
-
-
-
先遍历背包后遍历物品：
-
1）外层循环固定背包容量
-
在大小固定的背包里循环遍历添加物品，直到物品全遍历一次
-
-
2）物品遍历结束，外层背包容量+1
-
此时仍要执行内层循环，再次遍历一遍物品
-
可能会出现如下情况：
-
在上一轮遍历到物品3时，当前容量的背包已经没有办法塞入物品3，因此背包里此时有物品1和物品2
-
在当前轮遍历的时候发现增加了容量的背包可以再添加一个物品1，就会有【物品1，物品2，物品1】这样的情况，所以很可能会有物品1出现在物品2之类的情况
-
-
-
-
-
-
-
5.举例推导dp数组
-
手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的
-
【解题步骤】
-
1.创建一个dp数组，大小为amount+1
-
2.初始化dp数组，dp[0]= 1
-
3.先遍历物品，再遍历背包：
-
递推公式
-
-
4.return dp[amount]
【代码部分】
class Solution {
public int change(int amount, int[] coins) {
int [] dp = new int[amount + 1];
dp[0] = 1;
for(int i = 0 ; i < coins.length ; i++){
for(int j = coins[i] ; j <= amount ; j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}LeetCode 474 组合总和IV
题目链接：377. 组合总和 Ⅳ - 力扣（LeetCode）
【解题思路】
-
本题说是组合总和，但其实求的是排列数
-
因为（1,2,1)和(1,1,2)算两个组合
-
-
1.确定dp数组以及下标含义
-
dp[j]的定义是：装满容量为j的背包有dp[j]种方法
-
本题最终要求的是dp[amount]
-
-
2.确定递推公式
-
dp[j]+=dp[j-coins[i]]
-
-
3.确定dp数组如何初始化
-
dp[0]=1
-
因为要做累加，所以不能初始化为0
-
-
非0下标初始为0
-
-
4.确定遍历顺序
-
先遍历背包：
-
再遍历物品：
-
递推公式
-
-
-
因为本题求的是排列数
-
Carl说先遍历物品是组合数，先遍历背包是排列数，对于这点，我的理解是：
-
先遍历物品后遍历背包：
-
1）外层固定物品1，进入内层循环
-
2）背包容量不断增加
-
物品1被重复添加进不同容量的背包中，直到背包容量遍历完毕
-
-
3）背包容量遍历完毕后，执行下一次循环，开始添加物品2
-
物品1已经被添加进每一个不同容量的背包里，因此物品2肯定会在物品1之后
-
-
-
先遍历背包后遍历物品：
-
1）外层循环固定背包容量
-
在大小固定的背包里循环遍历添加物品，直到物品全遍历一次
-
-
2）物品遍历结束，外层背包容量+1
-
此时仍要执行内层循环，再次遍历一遍物品
-
可能会出现如下情况：
-
在上一轮遍历到物品3时，当前容量的背包已经没有办法塞入物品3，因此背包里此时有物品1和物品2
-
在当前轮遍历的时候发现增加了容量的背包可以再添加一个物品1，就会有【物品1，物品2，物品1】这样的情况，所以很可能会有物品1出现在物品2之类的情况
-
-
-
-
-
-
-
5.举例推导dp数组
-
手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的
-
【解题步骤】
-
1.创建一个dp数组，大小为amount+1
-
2.初始化dp数组，dp[0]= 1
-
3.先遍历物品，再遍历背包：
-
递推公式
-
-
4.return dp[amount]
【代码部分】
class Solution {
public int combinationSum4(int[] nums, int target) {
int [] dp = new int[target + 1];
dp[0] = 1;
for(int i = 0 ; i <= target ; i++){
for(int j = 0 ; j < nums.length ; j++){
if(i >=nums[j]){
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}