1049. 最后一块石头的重量II
题目简述：
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
思路：
1. 题目转化为背包问题，取数，使得和最接近sum//2，这个最接近的值为maxweight
2. 则最终结果为sum-2*maxweight
代码如下：
class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: total = sum(stones) n, m = len(stones), total // 2 dp = [[False] * (m + 1) for _ in range(n + 1)] dp[0][0] = True for i in range(n): for j in range(m + 1): if j < stones[i]: dp[i + 1][j] = dp[i][j] else: dp[i + 1][j] = dp[i][j] or dp[i][j - stones[i]] ans = None for maxweight in range(m, -1, -1): if dp[n][maxweight]: ans = total - 2 * maxweight break return ans
494. 目标和
题目简述：
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路：
1. 记数组和为sum，添加负号的元素之和为neg，则其余添加正号的元素之和为sum-neg
2. 得到的表达式结果为
(sum−neg)−neg=sum−2⋅neg=target
3. 则neg=(sum-target)/2
4. 由于数组nums中的元素都是非负整数，neg也必须是非负整数，所以要求sum-target是非负偶数，若不符合条件直接返回0
5. 问题转化为在数组nums中选取若干元素，使得这些元素之和等于neg，计算选取元素的方案数
6. 利用动态规划方法求解
7. 定义二维数组dp，其中dp[i][j]表示在数组nums的前i个数中选取元素，使得这些元素之和等于j的方案数。
8. 假设数组nums的长度为n，则最终答案为dp[n][neg]
9. 没有任何元素可选取，元素和只能为0，对应方案数是1，即dp[0][0]=1,dp[0][j]=0(j>=1)
10. 当1<=i<=n时，对于数组nums中的第i个元素num，遍历0<=j<=neg，计算dp[i][j]的值
1）如果j<num，则不能选num，又dp[i][j]=dp[i-1][j]
2) 如果j>=num，为选num和不选num两种情况，总和是dp[i][j]=dp[i-1][j]+dp[i-1][j-num]
11. 最终答案为dp[n][neg]
代码如下：
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: ''' pos + neg = total ''' ''' pos - neg = target ''' total = sum(nums) if abs(target) > total: # target可能为负 return 0 if (total + target) % 2 == 1: # 不能被2整除【对应于pos不是整数】 return 0 '''【0/1背包】：从nums中选出数字组成pos或neg''' pos = (total + target) // 2 neg = (total - target) // 2 capcity = min(pos, neg) # 取pos和neg中的较小者，以使得dp空间最小 n = len(nums) # 初始化 dp = [[0] * (capcity+1) for _ in range(n+1)] # dp[i][j]: 从前i个元素中选出若干个其和为j的方案数 dp[0][0] = 1 # 其他 dp[0][j]均为0 # 状态更新 for i in range(1, n+1): for j in range(capcity+1): if j < nums[i-1]: # 容量有限，无法选择第i个数字nums[i-1] dp[i][j] = dp[i-1][j] else: # 可选择第i个数字nums[i-1]，也可不选【两种方式之和】 dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]] return dp[n][capcity]
474. 一和零
题目简述：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
思路：
三维dp
1. 定义三维数组dp[i][j][k]，表示取数组的前i个元素参加操作，使得0的数量小于等于j，1的数量小于等于k，在这种条件约束下的最长子集
2. 进行分类讨论
代码如下：
class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: length = len(strs) dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(length+1)] for i in range(1, length+1): c0 = strs[i-1].count('0') # 当前字符串中0的数目 c1 = len(strs[i-1]) - c0 # 当前字符串中1的数目 for j in range(m+1): # 第二层循环：0的背包容量 for k in range(n+1): # 第三层循环：1的背包容量 if j < c0 or k < c1: # 无法添加当前字符串 dp[i][j][k] = dp[i-1][j][k] else: # 可选或不选当前字符串，取两者之间的较大值 dp[i][j][k] = max( dp[i-1][j][k], dp[i-1][j-c0][k-c1] + 1 ) return dp[length][m][n]