完全背包理论
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
示例：
背包最大重量为4。
物品为：
重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 每件商品都有无限个！
问背包能背的物品最大价值是多少？
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以这里还是以纯完全背包问题进行讲解理论和原理。
01背包和完全背包唯一不同就是体现在遍历顺序上，因此直接针对遍历顺序经行分析！01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次，而完全背包的物品是可以多次添加的，所以这里就要从小到达遍历。
其次是先后问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？
在01背包中，如果是定义了二维数组，则先遍历谁都可以，而定义一维数组后，两个for循环先后循序一定是先遍历物品，再遍历背包容量。
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：
因此，完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）
518.零钱兑换II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
- 输入: amount = 5, coins = [1, 2, 5]
- 输出: 4
解释: 有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
示例 2:
- 输入: amount = 3, coins = [2]
- 输出: 0
- 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
- 输入: amount = 10, coins = [10]
- 输出: 1
注意，你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
本题可以重复放入金币，也就是物品，因此属于完全背包问题。转换为背包问题就是：
- 确定dp数组以及下标的含义：dp[j]为凑成总金额j的货币组合数
- 确定递推公式：dp[j] 就是所有的dp[j - coins[i]]想加的情况。dp[j]+=dp[j-coins[i]]
- dp数组如何初始化：当金币总额为0的时候，就只有一种情况，不放入金币，所以dp[0]=1
- 确定遍历顺序：在完全背包中，先遍历背包或者物品都是可以的。因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，所以纯完全背包是能凑成总和就行，不用管怎么凑的。但本题要求凑成总和的组合数，元素之间明确要求没有顺序：那么如果外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况，假设：coins[0] = 1，coins[1] = 5。就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。所以这种遍历顺序中dp[j]里计算的是组合数！如果把两个for交换顺序，那么背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况，此时计算的是排列数，本题要求不重复，只计算组合数即可，所以需要先遍历物品，再遍历背包。
class Solution {
/**
dp[j]为凑成总金额j的货币组合数
dp[0]=1
dp[j]+=dp[j-coins[i]]
*/
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];
}
}377. 组合总和 Ⅳ
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
- nums = [1, 2, 3]
- target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7
本题可以重复放物品，所以为完全背包问题，思考下面五部曲：
- 确定dp数组以及下标的含义：dp[j]为凑成目标j的元素组合数
- 确定递推公式：dp[j]+=dp[j-nums[i]]
- dp数组如何初始化：dp[0]=1
- 确定遍历顺序：题里给的示例很明确的说民反，顺序不同的序列视作不同的组合，也就是{1,2}和{2,1}算两种组合，因此这里需要计算的是排列数，因此需要先遍历背包，再遍历物品。
本题再次强调的一点：
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0]=1;
//求排列个数，需要先遍历背包再遍历物品
for(int j=0;j<=target;j++){
for(int i=0;i<nums.length;i++){
if(j-nums[i]>=0 ) dp[j]+=dp[j-nums[i]];
}
}
return dp[target];
}
}
