长春网络建站模板,a站进入,电商网站建设哪家好,展览设计工程有限公司Day 43
1049.最后一块石头的重量II
本题中#xff0c;石头的重量是 stones[i]#xff0c;石头的价值也是 stones[i] #xff0c;可以 “最多可以装的价值为 dp[j]” “最多可以背的重量为dp[j]”
dp[j] max(dp[j], dp[j - stones[i]] stones[i]);
最后dp[target]里是…Day 43
1049.最后一块石头的重量II
本题中石头的重量是 stones[i]石头的价值也是 stones[i] 可以 “最多可以装的价值为 dp[j]” “最多可以背的重量为dp[j]”
dp[j] max(dp[j], dp[j - stones[i]] stones[i]);
最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]。
在计算target的时候target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
class Solution:def lastStoneWeightII(self, stones: List[int]) - int:dp [0] * 15001total sum(stones)target total // 2for stone in stones:for j in range(target, stone - 1, -1):dp[j] max(dp[j], dp[j - stone] stone)return total - dp[target] - dp[target]class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int i : stones) {sum i;}int target sum 1;//初始化dp数组int[] dp new int[target 1];for (int i 0; i stones.length; i) {//采用倒序for (int j target; j stones[i]; j--) {//两种情况要么放要么不放dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - 2 * dp[target];}
}494.目标和
本题要如何使表达式结果为target
既然为target那么就一定有 left组合 - right组合 target。
left right sum而sum是固定的。right sum - left
公式来了 left - (sum - left) target 推导出 left (target sum)/2 。
target是固定的sum是固定的left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
此时问题就转化为装满容量为x的背包有几种方法。
dp[j] 表示填满j包括j这么大容积的包有dp[j]种方法
只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。
例如dp[j]j 为5
已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包。已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
dp[j] dp[j - nums[i]]class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:total sum(nums)if abs(target) total:return 0if (target total) % 2 1:return 0tar_sum (target total) // 2dp [0] * (tar_sum 1)dp[0] 1for num in nums:for j in range(tar_sum, num - 1, -1):dp[j] dp[j - num]return dp[tar_sum]class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for (int i 0; i nums.length; i) sum nums[i];//如果target过大 sum将无法满足if ( target 0 sum -target) return 0;if ((target sum) % 2 ! 0) return 0;int size (target sum) / 2;if(size 0) size -size;int[] dp new int[size 1];dp[0] 1;for (int i 0; i nums.length; i) {for (int j size; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[size];}
}474.一和零
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) - int:dp [[0] * (n 1) for _ in range(m 1)]for s in strs:zeronum s.count(0)onenum s.count(1)for i in range(m, zeronum - 1, -1):for j in range(n, onenum - 1, -1):dp[i][j] max(dp[i][j], dp[i - zeronum][j - onenum] 1)return dp[m][n]
