今日任务：

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



资料来源：

1. [代码随想录 | 完全背包问题](https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html)
2. [代码随想录 | LeetCode518 零钱兑换Ⅱ](https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html)
3. [代码随想录 | LeetCode377 组合总和Ⅳ](https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html)

### 1 完全背包问题

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

### 2 LeetCode518 零钱兑换Ⅱ

:::info{title="题目"}
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

 

示例 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
```

提示：

- 1 <= coins.length <= 300
- 1 <= coins[i] <= 5000
- coins 中的所有值 互不相同
- 0 <= amount <= 5000
:::

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

![97ae849f87987c175c1107c3e54c1c0.jpg](https://www.misaka19327.cc/static/img/92a564d811032b02d75c361ad528b0ec.97ae849f87987c175c1107c3e54c1c0.jpg)

``` 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
```

:::tip{title="提示"}
另外，这题也是一种另类的爬楼梯，硬币就是可以爬的步长，总额就是楼梯长度。只是爬楼梯求的是排列，而这个题求的是组合罢了。
:::

### 3 LeetCode377 组合总和Ⅳ

:::info{title="题目"}
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

 

示例 1：
```
输入：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)
请注意，顺序不同的序列被视作不同的组合。
```
示例 2：
```
输入：nums = [9], target = 3
输出：0
 ```

提示：

- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- nums 中的所有元素 互不相同
- 1 <= target <= 1000
 

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
:::

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

``` 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]
}
```

代码随想录算法训练营第四十四天 | LeetCode518 零钱兑换Ⅱ、LeetCode377 组合总和Ⅳ

MisakaDB-kv型小型数据库 | 记录1

今日任务：

1. LeetCode1049 最后一块石头的重量Ⅱ
2. LeetCode494 目标和
3. LeetCode474 一和零



资料来源：

1. [代码随想录 | LeetCode1049 最后一块石头的重量Ⅱ](https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html)
2. [代码随想录 | LeetCode494 目标和](https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html)
3. [代码随想录 | LeetCode474 一和零](https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html)

### 1 LeetCode1049 最后一块石头的重量Ⅱ

:::info{title="题目"}
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

 

示例 1：
```
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
```
示例 2：
```
输入：stones = [31,26,33,21,40]
输出：5
```

提示：

- 1 <= stones.length <= 30
- 1 <= stones[i] <= 100
:::

我对着这题看了半天，愣没看出来哪里有背包。资料一语点醒梦中人：

> 本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

我：

![b303350d84ce8705397b8c6b2c5e8436.jpg](https://www.misaka19327.cc/static/img/e518e177f3ea97e3e8fa5a6edabf354a.b303350d84ce8705397b8c6b2c5e8436.jpg)

``` go
func lastStoneWeightII(stones []int) int {
	sum := 0
	for _, value := range stones {
		sum += value
	}
	target := sum / 2
	dp_array := make([]int, target + 1)
	for _, stone := range stones {
		for j := target; j >= stone; j-- {
			dp_array[j] = max(dp_array[j], dp_array[j - stone] + stone)
		}
	}
	return sum - dp_array[target] - dp_array[target] // 前俩算出来的是这么一大堆石头的另一半 最后再减去的是上面进行dp的目标 即求能组成的最靠近一半石头大小的石头组合
}
```

### 2 LeetCode494 目标和

:::info{title="题目"}
给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

 

示例 1：
```
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
```
示例 2：
```
输入：nums = [1], target = 1
输出：1
```

提示：

- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
:::

既然运算符只有加号和减号，那事情就好办了。数字无外乎加减，也就是说只要要加的那些的总和减去要减的那些的总和等于target就行了。再转换一下，要减的那些是所有元素的总和减去要加的那些。也就是说，要加的那些元素的总和x，所有元素的总和sum和target，存在一个$$x - (sum - x) = target$$，也就是$$2x - sum = target$$。一旦确定要求的是“从给定的数组中提取一些元素，使得总和x等于$$(sum + target) / 2$$”即可。

``` go
func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, value := range nums {
		sum += value
	}
	if int(math.Abs(float64(target))) > sum || (target + sum) % 2 != 0 {
		return 0 // 必然无解 不能取整也是无解 可以以sum为5 target为2为例想一下
	}
        // 另外 sum == abs(target)不意味着只有一种方式 因为存在0的问题 0无论加减都不会影响总和
	dpTarget := (target + sum) / 2
	dpArray := make([]int, dpTarget + 1)
	dpArray[0] = 1
	for i := 0; i < len(nums); i++ {
		for j := dpTarget; j >= nums[i]; j-- {
			dpArray[j] += dpArray[j - nums[i]]
		}
	}
	return dpArray[dpTarget]
}
```

### 3 LeetCode474 一和零

:::info{title="题目"}
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

 

示例 1：
```
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
```
示例 2：
```
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
```

提示：

- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] 仅由 '0' 和 '1' 组成
- 1 <= m, n <= 100
:::

~~那谁还能想到价值也能变成二维的价值呢。~~

这个确实是01背包，因为子集元素只能取一次。但是和01背包对应还是有点难对上。背包指的是子集，给定的strs里的每个元素就是物品，重量恒定为1，**质量却有两个维度：0的个数和1的个数**，所以写01背包往前查的时候必须按两个维度往前查才可以！

``` go
func findMaxForm(strs []string, m int, n int) int {
	dpArray := make([][]int, m + 1)
	for value := range dpArray {
		dpArray[value] = make([]int, n + 1)
	}
	for _, str := range strs {
		zeroNum, oneNum := 0, 0 // 统计0和1的个数
		for _, char := range str {
			if char == '0' {
				zeroNum += 1
			} else {
				oneNum += 1
			}
		}
                // 虽然dpArray是二维的 但是因为“物品”的价值也是二维的 所以写法一定是一维的
		for i := m; i >= zeroNum; i-- {
			for j := n; j >= oneNum; j-- {
				dpArray[i][j] = max(dpArray[i][j], dpArray[i - zeroNum][j - oneNum] + 1) // 从两个维度往前查
			}
		}
	}
	return dpArray[m][n]
}
```