文章目录
- 416.分割等和子集
- 3489.零数组变换IV
0-1背包问题就是选择与不选择的问题，从根本上来讲的话，就是一个可以不连续的子集target问题，如果考虑的是一定得连续的问题，那么就可以考虑的是不定长滑动窗口的问题
416.分割等和子集
416.分割等和子集
- 分割为两个等和的子集，那么我们可以转化为只用选择一个子集的问题，那么剩余的子集就是总和减去当前子集的和
- 考虑到等和的问题，所以
首先求解出sum(nums),如果为奇数，那么肯定是不能成功分解的，如果是偶数，就可以转化为，在原本的nums数组中，能否找到和为target//2的组合？ - 注意
dp数组的初始化，dp[i][0]都是True
class Solution:def canPartition(self, nums: List[int]) -> bool:# 其实就是0-1背包问题，target 是一半，所以sum得是偶数sumnums = sum(nums)if sumnums % 2 == 1:return Falsetarget = sumnums // 2n = len(nums)# 现在的话就是一个经典的0-1背包问题# 其实可以定义dp[i][j]表示为前i个物品中，是否可以组成jdp = [[True]+[False]*target for _ in range(n)]for i in range(n):for j in range(1,target+1):if j < nums[i] :dp[i][j] = dp[i-1][j]else:dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]return dp[n-1][target]3489.零数组变换IV
3489.零数组变换IV
- 注意这个问题，我开始思考的是前缀和与差分，但是没考虑到题目中的
选择范围是[l,r]的范围中的子集进行操作，那么就是说明对于每一个数的操作是独立的！ - 只要我们在对应的
操作数组中能够得到这个nums[i]的组合，那么就可以说明nums[i]是可以组合成功的，所以，我们可以转化为这个416.分割等和子集的问题，不过对应修改为能否在对应的pack[i]中得到nums[i]的组合？
class Solution:def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:# 别人做的太复杂了，能不能直接转化为这个 subnums的问题n = len(nums)# 就是得开n个背包pack = [[] for _ in range(n)]m = len(queries)if sum(nums) == 0:return 0# 多个背包问题，然后求解的是是否都满足？都满足的情况下，找到最少的情况下的最大的那个所需的物品数def check(num,target):n1 = len(num)dp = [[True]+[False]*target for _ in range(n1)]for i in range(n1):for j in range(1,target+1):if j < num[i]:dp[i][j] = dp[i-1][j]else:dp[i][j] = dp[i-1][j] or dp[i-1][j-num[i]]if dp[i][target]:return i+1return -1# 得到对应的一个物品的列表for l,r,v in queries:for i in range(n):if l<= i <=r:pack[i].append(v)else:pack[i].append(0)minans = 0for i in range(n):# 每一个背包都进行遍历cnt = check(pack[i],nums[i])if cnt == -1:return -1else:minans = max(minans,cnt)return minans
