更弱智的算法学习 day36
1049. 最后一块石头的重量 II
可以这么理解，有一个target = sums // 2，也即有一个目标数组和的一半，把他视为石头一半重量，想要达到的最大价值也即石头一般的重量，每个石头的价值和重量都是他本身。
- 确定dp数组（dp table）以及下标的含义定义
dp[j]数组表示，石头的当前总重量为j时（也即总目标减去消耗的数值），所能得到的最大值
- 确定递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
还是同样的 dp[j] = max(dp[j], dp[j-nums[j]] + nums[j])
还是同样的dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
- dp数组如何初始化
全初始化为0
- 确定遍历顺序
先顺序遍历道具，在反向遍历背包重量
- 举例推导dp数组
class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: sums = sum(stones) target = sums // 2 dp = [0] * (target + 1) for i in range(len(stones)): for j in range(target, stones[i]-1, -1): dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]) return sums-dp[target]*2494. 目标和
设所有数字的总和为
sum_nums。我们将添加+的数字集合记为P，其和为plus_sum；添加-的数字集合记为N，其和为minus_sum。则有：plus_sum + minus_sum = sum_nums (1) plus_sum - minus_sum = target (2)从上述方程可以推导出两种等价的转化：
求正数子集和：由 (1) + (2) 得：
2 * plus_sum = sum_nums + target plus_sum = (sum_nums + target) / 2问题转化为：从
nums中选取若干数字，使其和为(sum_nums + target)/2。求负数子集和：由 (1) - (2) 得：
2 * minus_sum = sum_nums - target minus_sum = (sum_nums - target) / 2问题转化为：从
nums中选取若干数字，使其和为(sum_nums - target)/2
- 确定dp数组（dp table）以及下标的含义定义
dp[j]数组表示，选取的数字和为
j的方法数
- 确定递推公式
dp[j] += dp[j - num]这里其实就是dp[j] = dp[j]+dp[j-num]
有选num这个数和不选num这个数两种方法：选了就是dp[j]；不选就是dp[j-num]
- dp数组如何初始化
dp[0] = 1，由于数都大于0，取0的方法只有一种，就是全都不取
s < 0：表示abs(target)大于总和，无法实现。
s % 2 == 1：表示s是奇数，则new_target = s//2不是整数，而数字和必须是整数。
- 确定遍历顺序
先顺序遍历数，在遍历背包大小，也即还剩多少数
- 举例推导dp数组
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: s = sum(nums)-abs(target) if s<0 or s%2==1: return 0 new_target = s//2 dp = [0] * (new_target + 1) dp[0] = 1 for i in range(len(nums)): for j in range(new_target, nums[i]-1, -1): dp[j] += dp[j-nums[i]] return dp[new_target]474.一和零
相当于背包有两层约束，0和1的数量都不能超了
- 确定dp数组（dp table）以及下标的含义定义
dp[p][q]数组表示，还剩余可用的p个0和q个1在strs中的最大子集的长度
- 确定递推公式
显然选择只有两种，选择把strs加入子集和不加入子集，加入子集要消耗对应的0的数量和1的数量，然后子集长度+1,在前面计算好保存在二维数组中了。不加入子集就没有变化。
dp[p][q] = max(dp[p-number[i][0]][q-number[i][1]] + 1,dp[p][q])
- dp数组如何初始化
都归化为0即可
- 确定遍历顺序
先顺序遍历字符串，在遍历背包大小的两个维度约束
- 举例推导dp数组
class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: number = [] for k in range(len(strs)): num0 = strs[k].count('0') num1 = strs[k].count('1') number.append([num0, num1]) dp = [[0] * (n+1) for _ in range(m+1)] for i in range(len(number)): for p in range(m, number[i][0]-1, -1): for q in range(n, number[i][1]-1, -1): dp[p][q] = max(dp[p-number[i][0]][q-number[i][1]] + 1,dp[p][q]) return dp[m][n]可以通过下面的方法来简化数组的使用，但是差别不大
class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: f = [[0] * (n + 1) for _ in range(m + 1)] for s in strs: cnt0 = s.count('0') cnt1 = len(s) - cnt0 for j in range(m, cnt0 - 1, -1): for k in range(n, cnt1 - 1, -1): f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1) return f[m][n]