今日任务：

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

资料来源：

1. 代码随想录 | LeetCode1049 最后一块石头的重量Ⅱ
2. 代码随想录 | LeetCode494 目标和
3. 代码随想录 | LeetCode474 一和零

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

输入：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]，这就是最优值。

输入：stones = [31,26,33,21,40]
输出：5

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

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

我：

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 目标和

输入：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

输入：nums = [1], target = 1
输出：1

既然运算符只有加号和减号，那事情就好办了。数字无外乎加减，也就是说只要要加的那些的总和减去要减的那些的总和等于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 一和零

输入：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 。

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

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

这个确实是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]
}