今日任务：
1）1049. 最后一块石头的重量 II
2）494. 目标和
3）474.一和零
4）复习day12
1049. 最后一块石头的重量 II
题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）
题目难度：中等 有一堆石头，每块石头的重量都是正整数。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。 示例： 输入：[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]，这就是最优值。 提示： 1 <= stones.length <= 30 1 <= stones[i] <= 1000
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之背包问题，这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II哔哩哔哩bilibili
思路：
- 首先，我们需要确定背包的最大承重，即石头总重量的一半，因为我们需要将石头分成两部分，使得它们的重量尽可能接近。
- 创建一个动态规划数组
dp，长度为背包最大承重加一，初始化为零。dp[i]表示在不超过承重i的情况下，可以得到的最大石头重量之和。- 遍历每块石头，对于每块石头，逆序遍历动态规划数组，更新
dp[j]的值，其中j >= stone，表示当前石头可以放入背包的情况下，更新最大重量。- 最后，计算剩余石头的最小可能重量，即总重量减去动态规划数组中的最大值，再减去动态规划数组中的最大值。
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
sum_ = sum(stones)
target = sum_ // 2
dp = [0] * (target + 1)
# 动态规划更新
for stone in stones:
for j in range(target, stone - 1, -1):
dp[j] = max(dp[j], dp[j - stone] + stone)
# 计算最小可能的石头重量
return (sum_ - dp[target]) - dp[target]494. 目标和
题目链接：494. 目标和 - 力扣（LeetCode）
难度：中等 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例： 输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5 解释： -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 一共有5种方法让最终目标和为3。 提示： 数组非空，且长度不会超过 20 。 初始的数组的和不会超过 1000 。 保证返回的最终结果能被 32 位整数存下
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和哔哩哔哩bilibili
思路：
本题要如何使表达式结果为target
既然为target，那么就一定有 正数组合 - 负数组合 = target
add_sum + sub_sum = sum
target = add_sum - sub_sum
=> add_sum = (sum + target) / 2
sub_sum = (sum - target) / 2
target是固定的，sum是固定的，
此时问题就是在集合nums中找出和为add_sum(或sub_sum)的组合
1.计算总和： 首先，计算数组
nums的总和total_sum。2.判断是否存在方案： 如果目标数的绝对值大于总和，或者目标数与总和的和为奇数，则不存在方案，直接返回0。
3.确定加法和： 将目标数与总和的和除以2，得到加法和
add_sum，因为我们要求的是所有添加符号的方法数。4.动态规划更新： 创建一个动态规划数组
dp，其长度为加法和加 1，初始化为0。遍历nums数组中的每个数，逆序遍历动态规划数组，更新动态规划数组中每个位置的值，表示达到该位置和的方案数。5.返回结果： 返回动态规划数组的最后一个元素，即达到目标和的方案数。
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
nums = [1,1,1,1,1]
target = 3
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 计算nums的总和
total_sum = sum(nums)
# 此时没有方案
if abs(target) > total_sum:
return 0
if (target + total_sum) % 2 == 1:
return 0
# 加法和
add_sum = (target + total_sum) // 2
# 创建动态规划数组，初始化为0
dp = [0]*(add_sum+1)
# 当目标和为0时，只有一种方案，即什么都不选
dp[0] = 1
# print(dp)
for num in nums:
for j in range(add_sum,num -1 ,-1):
print(num,j)
# 状态转移方程，累加不同选择方式的数量
dp[j] = dp[j] + dp[j-num]
# print(dp)
# 返回达到目标和的方案数
return dp[-1]474.一和零
题目链接：474. 一和零 - 力扣（LeetCode）
给你一个二进制字符串数组 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
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之背包问题，装满这个背包最多用多少个物品？| LeetCode：474.一和零哔哩哔哩bilibili
思路：
1.初始化动态规划数组： 创建一个二维动态规划数组
dp，其大小为(m+1) x (n+1)，并将所有元素初始化为0。这里dp[i][j]表示在最多有i个0和j个1的情况下，最大子集的大小。strs,m,n = ["10","0001","111001","1","0"], 3,3
2.遍历物品： 对于给定的字符串数组
strs，遍历其中的每个字符串。3.统计0和1的个数： 对于当前遍历的字符串
s，统计其中0和1的个数，分别记录为zeros和ones。4.动态规划更新： 使用二维动态规划进行更新。从最大容量开始逆序遍历到当前字符串中0和1的个数，根据状态转移方程
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)更新动态规划数组中的值。(符合要求，就在dp[i - zeros][j - ones]上加1，不符合要求就继承原来的值)
5.返回结果： 最后返回动态规划数组右下角元素的值，即最大子集的大小。
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(m + 1)] # 创建二维动态规划数组，初始化为0
# print(dp)
# 遍历物品
for s in strs:
ones = s.count('1') # 统计字符串中1的个数
zeros = s.count('0') # 统计字符串中0的个数
# 遍历背包容量且从后向前遍历
for i in range(m, zeros - 1, -1):
for j in range(n, ones - 1, -1):
# 状态转移方程，符合要求，就在dp[i - zeros][j - ones]上加1，不符合要求就继承原来的值
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
# print(dp)
return dp[m][n]
