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] * 15001
total = sum(stones)
target = total // 2
for 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,文章来源:https://www.toymoban.com/news/detail-646020.html
- 已经有一个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]] 累加起来。文章来源地址https://www.toymoban.com/news/detail-646020.html
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 0
if (target + total) % 2 == 1:
return 0
tar_sum = (target + total) // 2
dp = [0] * (tar_sum + 1)
dp[0] = 1
for 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]
到了这里,关于Day 43的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!