Day 43

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，

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[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]