今日任务：

1. 完全背包问题
2. LeetCode518 零钱兑换Ⅱ
3. LeetCode377 组合总和Ⅳ

资料来源：

1. 代码随想录 | 完全背包问题
2. 代码随想录 | LeetCode518 零钱兑换Ⅱ
3. 代码随想录 | LeetCode377 组合总和Ⅳ

1 完全背包问题

完全背包问题，就是在01背包的基础上，不限制物品的数量得到的问题类型。每种物品都可以取无限次，然后求背包能够带走的最大重量。还记得01背包的一维数组的求法中，第二层对背包的循环必须是倒序，以防止一个物品被添加多次这件事吗？完全背包的解法就是，第二层对背包的循环是正序，一个物品就可以被添加多次了。另外，完全背包的两层循环可以互相转换先后顺序，是先对背包循环还是先对物品循环都可以。

2 LeetCode518 零钱兑换Ⅱ

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

输入：amount = 10, coins = [10] 
输出：1

这题是一个很经典的完全背包问题，但是又不完全经典，主要区别是要区分求组合还是求排列的问题。求组合，就必须先遍历物品，再遍历背包；求排列，就必须先遍历背包，再遍历物品。原因的话，个人认为是先遍历背包再考虑物品的话，在遍历背包循环的下一轮，一定会重复考虑遍历背包循环的上一轮中选过的物品。比如说都是硬币1、2、5，都是要求总和为3，如果先遍历背包再考虑物品，那么2、1这个组合考虑之后，1、2也会被考虑进去，因为对物品的循环已经从1到2了，而之前的2，1是上一轮遍历背包时已经确定的。

go
func change(amount int, coins []int) int {
	dpArray := make([]int, amount + 1)
	dpArray[0] = 1
	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dpArray[i] += dpArray[i - coin]
		}
	}
	return dpArray[amount]
}

go
// 这是先遍历背包 再遍历物品的版本
func change(amount int, coins []int) int {
	dpArray := make([]int, amount + 1)
	dpArray[0] = 1
	for i := 1; i <= amount; i++ {
		for j := 0; j < len(coins); j++ {
			if i < coins[j] {
				continue
			}
			dpArray[i] += dpArray[i - coins[j]]
			fmt.Println(dpArray)
		}
	}
	return dpArray[amount]
}

先遍历物品 再遍历背包：

		[1 0 0 0 0 0] // 这是初始化 没有硬币 背包容量为0 可以认为是一种装法
		[1 1 0 0 0 0]
		[1 1 1 0 0 0]
		[1 1 1 1 0 0]
		[1 1 1 1 1 0]
		[1 1 1 1 1 1] // 到这是遍历硬币1 所有背包要装满都只有1种方法
		[1 1 2 1 1 1] 
		[1 1 2 2 1 1]
		[1 1 2 2 3 1]
		[1 1 2 2 3 3] // 到这是遍历硬币2
		[1 1 2 2 3 4] // 到这是遍历硬币5

在这个遍历方式下 一定是先出所有背包容量下 无限取硬币1装满的所有组合 再出无限取硬币1和2装满的所有组合

第一轮遍历对硬币1进行取舍中 所有背包都是先硬币1装满 只有这一种组合

第二轮遍历对硬币2进行取舍中 一定是在考虑了取不取硬币1之后再考虑的 所以只会出[1, 2]这种排列 不会出现[2, 1]这种排列 所以[1, 2]只会计入1次组合数

如果是先遍历背包 再遍历物品：

		[1 1 0 0 0 0] // 初始化 同上
		[1 1 0 0 0 0] // 对背包的第一轮循环开始 只能在背包容量为1的情况下 只能装1
		[1 1 1 0 0 0] // 对背包的第二轮循环开始
		[1 1 2 0 0 0] // dp[2] 对应11和2两种排列
		[1 1 2 2 0 0] // 对背包的第三轮循环开始 此时的dp[3]记录的是dp[2]外加硬币1的排列法 也就是111和21
		[1 1 2 3 0 0] // dp[3] 对应111，21，和12 这个12是在对物品循环到硬币2时 向前找到dp[1]时找到的排列法 也是一种新的排列
		[1 1 2 3 3 0] // 对背包的第四轮循环开始 此时的dp[4]记录的是dp[3]外加硬币1的排列法 也就是1111，211和121
		[1 1 2 3 5 0] // dp[4] 对应1111，211，121，112和22 后两个是在对物品循环到硬币2时 向前找到dp[2]时找到的排列法
		[1 1 2 3 5 5] // 对背包的第五轮循环开始 此时的dp[5]记录的是dp[4]外加硬币1的排列法 也就是11111，2111，1211，1121，221
		[1 1 2 3 5 8] // 对物品循环到硬币2时 向前找到dp[3]外加硬币2的排列法 即1112，212，122
		[1 1 2 3 5 9] // 对物品循环到硬币5时 向前找到dp[0]外加硬币5的排列法 即5
			      // 所以最后 dp[5]表示的是11111，2111，1211，1121，221，1112，212，122，5

3 LeetCode377 组合总和Ⅳ

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

输入：nums = [9], target = 3
输出：0

如果写明白上面那个题，这个题就容易多了。上面那个题是求组合，这个就是求排列。

go
func combinationSum4(nums []int, target int) int {
	dpArray := make([]int, target + 1)
	dpArray[0] = 1
	for i := 1; i <= target; i++ {
		for _, num := range nums {
			if i < num {
				continue
			}
			dpArray[i] += dpArray[i - num]
		}
	}
	return dpArray[target]
}