企业官网建设流程全解析

闵行专业做网站,怎么制作图片文件夹,厦门人才网唯一官方网站,万网网站后台管理1049. 最后一块石头的重量 II 可以这么理解#xff0c;有一个target sums // 2#xff0c;也即有一个目标数组和的一半#xff0c;把他视为石头一半重量#xff0c;想要达到的最大价值也即石头一般的重量#xff0c;每个石头的价值和重量都是他本身。 确定dp数组#x…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 s0 or s%21: 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] * (n1) for _ in range(m1)] 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]