算法训练营day36 动态规划④ 1049. 最后一块石头的重量 II、494. 目标和、474.一和零

        动态规划的第四篇博客，（各种各样的）01背包，每个元素只能用一次！

        494. 目标和 这道题是真的难啊，这是我代码随想录目前为止最让我觉得困难的一道题，主要是太难想到了（单纯对于一维的拓展方法来说，是很精妙的方法），当我后面浪费时间看了二维的理解之后，我的疑问是为什么二维反而比一维要难理解好多啊，这二维的方法好恶心啊，按理说因该是一样的呀

        二维和一维的普通理解方法我放弃了，因为我觉得二维方法中背包容量是一个很难理解的概念，所以这道题我只认可一维的解法

        简单总结下来：需要注意对于递归规律的理解（与dp数组高度相关)，二维一维区别的理解（虽然看起来简单，但是很重要）

1049. 最后一块石头的重量 II

        本题其实是尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的。

        一堆的石头重量是sum，那么我们就尽可能拼成 重量为 sum / 2 的石头堆。 这样剩下的石头堆也是 尽可能接近 sum/2 的重量。 那么此时问题就是有一堆石头，每个石头都有自己的重量，是否可以 装满 最大重量为 sum / 2的背包。

• 确定dp数组以及下标的含义

        dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。

• 确定递推公式

        本题是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); 比较普通的公式，但是公式一定要理解，每个石头逐个遍历，积累最大值，因为每个石头只有放入和不放入两个选择

• dp数组如何初始化

        因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。

• 确定遍历顺序

        如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

• 过程模拟如下：

        上期最后的题目416相当于是求背包是否正好装满，而本题是求背包最多能装多少（以此来求相撞之后的最小值）

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:dp = [0] * 15001total_sum = sum(stones)target = total_sum // 2for stones in stones:for j in range(target, stones - 1, -1):# 左闭右开 注意剪枝到stones - 1dp[j] = max(dp[j], dp[j - stones] + stones)return total_sum - dp[target] - dp[target]

494. 目标和

        假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target，即：x = (target + sum) / 2。此时问题就转化为，用nums装满容量为x的背包，有几种方法。

动态规划

• 确定dp数组以及下标的含义

         dp[j]，表示：填满j（包括j）这么大容积的包，有dp[j]种方法。

• 确定递推公式        

1. 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
2. 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
3. 已经有一个3（nums[i]） 的话，有 dp[2]种方法 凑成 容量为5的背包
4. 已经有一个4（nums[i]） 的话，有 dp[1]种方法 凑成 容量为5的背包
5. 已经有一个5 （nums[i]）的话，有 dp[0]种方法 凑成 容量为5的背包

        那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

• dp数组如何初始化

        这里dp[0] 初始为1 ,即装满背包为0的方法有一种，放0件物品。

        同时要理解的是，这个方法里求的数组为正数数组，不用考虑一个0要给+-号的区别，因为是对应的，和组合一样，所以只需要初始化dp[0]即可

• 确定遍历顺序

        遍历物品放在外循环，遍历背包在内循环，且内循环倒序（为了保证物品只使用一次）

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)if abs(target) > total_sum:return 0if (target + total_sum) % 2 == 1:return 0# 以上都是比较好理解的前置部分target_sum = (target + total_sum) // 2 # 目标和dp = [0] * (target_sum + 1)# 动态规划数组dp[0] = 1 # 这个位置需要重点理解, 这里赋值为1配合递推公式for num in nums:for j in range(target_sum, num - 1, -1):dp[j] += dp[j - num]# 很精妙的递推公式# 通过逐个遍历数组积累到最后return dp[target_sum]

回溯算法（超时）

        代码中不需要显式处理负数，而是通过 “是否选入子集” 的逻辑，间接包含了负数的情况。这个是核心要注意的

class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total == target:result.append(path[:])  # 将当前路径的副本添加到结果中# 如果 sum + candidates[i] > target，则停止遍历for i in range(startIndex, len(candidates)):if total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i + 1, path, result)total -= candidates[i]path.pop()def findTargetSumWays(self, nums: List[int], target: int) -> int:total = sum(nums)if target > total:return 0  # 此时没有方案if (target + total) % 2 != 0:return 0  # 此时没有方案，两个整数相加时要注意数值溢出的问题bagSize = (target + total) // 2  # 转化为组合总和问题，bagSize就是目标和# 以下是回溯法代码result = []nums.sort()  # 需要对nums进行排序self.backtracking(nums, bagSize, 0, 0, [], result)return len(result)

474.一和零

        本题中strs 数组里的元素就是物品，每个物品都是一个！而m 和 n相当于是一个背包，两个维度的背包。是使用了两个维度的‘一维背包解法’

• 确定dp数组（dp table）以及下标的含义

        dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

• 确定递推公式

        所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);不难理解

• dp数组如何初始化

        因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

• 确定遍历顺序

        因为是“一维解法”，01背包一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0] * (n + 1) for _ in range(m + 1)]  # 创建二维动态规划数组，初始化为0for s in strs:zeroNum = s.count('0')oneNum = len(s) - zeroNumfor i in range(m, zeroNum - 1, -1):for j in range(n, oneNum - 1, -1):dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)# 不断检查-z-o位置的个数, 如果大于自己会覆盖return dp[m][n]