Day43|动态规划part05: 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

这篇具有很好参考价值的文章主要介绍了Day43|动态规划part05: 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1049. 最后一块石头的重量 II

本题物品的重量为stones[i],物品的价值也为stones[i]。

对应着01背包里的物品重量weight[i]和 物品价值value[i]。

  1. 确定dp数组以及下标的含义

dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]

  1. 确定递推公式

01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);(与分割子集那题相同)

  1. dp数组如何初始化

既然 dp[j]中的j表示容量,那么最大容量(重量)(也就是target)是多少呢,就是所有石头的重量和。

定为target15001即可, 也可以将数组相加再/2

  1. 确定遍历顺序

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中就已经说明:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!

  1. 举例推导dp数组
  2. 从0-1背包转化成实际问题

最后dp[target]里是容量为target的背包所能背的最大重量。

那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。

在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

最终代码:

class Solution {
    public int lastStoneWeightII(int[] stones) {
        //思想:让重量相似的石头相撞这样得到的石头更小
        int sum = 0;
        for(int stone : stones){
            sum += stone;
        }
        int target = sum / 2;//像下取整的,target一定小于等于sum - target
        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 - dp[target] - dp[target];

    }
}

494. 目标和

这题的重点在于怎么把正负符号问题转化为定和->进而转化为0-1背包问题

本题要如何使表达式结果为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的组合。(相当于0-1背包问题)

有两种解法,一个回溯,跟组合总和那题一样,第二种解法就是动态规划。

回溯

先空着,不剪枝会超时。

动态规划

x = (target + sum) / 2

此时问题就转化为,装满容量为x的背包,有几种方法

dp五部曲

  1. 确定dp数组下标及其含义

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

  1. 确定递推公式

只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。也就是说dp[j - nums[i]]渴望找到nums[i],这样就符合要求了。因此递推公式是:

所以求组合类问题的公式,都是类似这种:

dp[j] += dp[j - nums[i]]

这个公式在后面在讲解背包解决排列组合问题的时候还会用到!

  1. 初始化dp数组

只要初始化dp[0]即可,填满0的包,有1种方法,所以dp[0] = 1。

  1. 确定遍历顺序

跟之前的一维0-1背包一样,先遍历物品再遍历背包,背包从后往前遍历。

  1. 举例推导dp数组

[外链图片转存中…(img-PMOiMxzQ-1713323607584)]

最终代码:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        //如果target的绝对值大于sum,那么是没有方案的
        if (Math.abs(target) > sum) return 0;
        //如果(target+sum)除以2的余数不为0,也是没有方案的
        if ((target + sum) % 2 == 1) return 0;
        

        int left = (sum + target) / 2;

        int dp[] = new int[left + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.length;i++){
            for(int j = left; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
}

这里注意两个特殊情况, 一个是如果target的绝对值大于sum,那么是没有方案的,另一个是如果(target+sum)除以2的余数不为0,也是没有方案的。

474. 一和零

理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。

但本题其实是01背包问题!

只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。

dp五部曲

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

  1. 确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

  1. dp数组初始化

初始为0即可。

  1. 遍历顺序

外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!文章来源地址https://www.toymoban.com/news/detail-855952.html

for (string str : strs) { // 遍历物品
    int oneNum = 0, zeroNum = 0;
    for (char c : str) {
        if (c == '0') zeroNum++;
        else oneNum++;
    }
    for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!
        for (int j = n; j >= oneNum; j--) {
            dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
    }
}
  1. 举例推导dp数组
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]表示i个0和j个1时的最大子集
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            //倒序遍历
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

到了这里,关于Day43|动态规划part05: 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Day43|leetcode 1049.最后一块石头的重量II、494.目标和、474.一和零

    题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 视频链接:动态规划之背包问题,这个背包最多能装多少?LeetCode:1049.最后一块石头的重量II_哔哩哔哩_bilibili 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设

    2024年02月10日
    浏览(51)
  • 力扣第1049题 最后一块石头的重量Il c++ 动态规划(01背包)

    1049. 最后一块石头的重量 II 中等 相关标签 有一堆石头,用整数数组  stones  表示。其中  stones[i]  表示第  i  块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x  和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x

    2024年02月06日
    浏览(45)
  • 力扣:416. 分割等和子集 & 1049. 最后一块石头的重量 II (动态规划)(二合一,一次吃透两道题)

    力扣:416. 分割等和子集 1049. 最后一块石头的重量 II 用的方法都是01背包解法,思路也是近乎一样,这里就放在一起讲解了(主要讲解第一题,第二题大家可以直接自己AC)。01背包解法详细讲解请见上篇博客01背包问题(二) 给你一个 只包含正整数 的 非空 数组 nums 。请你判断

    2024年01月20日
    浏览(50)
  • 【5.31 代随_43day】 最后一块石头的重量 II、目标和、一和零

    力扣连接:1049. 最后一块石头的重量 II(中等) 和 416. 分割等和子集 (opens new window) 非常像了 图解步骤 代码 力扣连接:494. 目标和(中等) 确定dp数组以及下标的含义 dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法 确定递推公式 只要搞到nums[i],凑成dp[j]就有dp[

    2024年02月07日
    浏览(48)
  • LeetCode1049. 最后一块石头的重量 II

    一、题目 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为 x 和 y ,且 x = y 。那么粉碎的可能结果如下: 如果 x == y ,那么两块石头都会被完全粉碎; 如果 x != y ,

    2024年02月10日
    浏览(38)
  • Leetcode 1049 最后一块石头的重量II

    题意理解 :         有一堆石头,用整数数组  stones  表示。其中  stones[i]  表示第  i  块石头的重量。         每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x  和  y ,且  x = y 。         思路转化:我们可以将题目转换为

    2024年01月16日
    浏览(39)
  • LeetCode 1049 最后一块石头的重量 II

    题目: 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x = y。那么粉碎的可能结果如下: 如果 x == y,那么两块石头都会被完全粉碎; 如果 x != y,那么重

    2024年02月05日
    浏览(45)
  • leetcode 1049. 最后一块石头的重量 II

             与分割等和子集类似,可以转化为0-1背包问题。 本题也是需要将数组元素分成两堆,区别在于本题需要使这两堆的差值最小,而之前那题是需要两堆差值为0。          使用之前的一维dp数组的思路,代码如下:

    2024年02月13日
    浏览(44)
  • Leet code1049 最后一块石头的重量II

    1049 最后一块石头的重量II 【问题描述】 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为 x 和 y ,且 x = y 。那么粉碎的可能结果如下: 如果 x == y ,那么两块石头

    2024年02月13日
    浏览(43)
  • leetcode 动态规划(最后一块石头的重量II、目标和、一和零)

    力扣题目链接(opens new window) 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x = y。那么粉碎的可能结果如下: 如果 x == y,那么两块石头都会被完全粉碎; 如果 x != y,那

    2024年02月03日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包