代码随想录算法训练营第43天 | 1049.最后一块石头的重量II ,494.目标和,474.一和零

动态规划章节理论基础:

https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

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

题目链接:https://leetcode.cn/problems/last-stone-weight-ii/

思路:

本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了,和昨天的416.分割等和子集 非常像。
本题物品的重量为stones[i],物品的价值也为stones[i]。对应着01背包里的物品重量weight[i]和 物品价值value[i]。

动规五部曲:
(1)确定dp数组以及下标含义
dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。

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

本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

(3)dp数组初始化
dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。

可以把石头遍历一遍,计算出石头总重量 然后除2,得到dp数组的大小。

(4)确定遍历顺序
如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历。

(5)举例推导dp数组
举例,输入:[2,4,1,1],此时target = (2 + 4 + 1 + 1)/2 = 4 ,dp数组状态图如下:
在这里插入图片描述
最后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 i:stones)
            sum += i;
        // 把石头分成两堆
        int target = sum >> 1;
        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]);
        }
        // 一堆是dp[target] , 那么另一堆一定是sum - dp[target]
        // 同时target是向下取整的,因此 sum - dp[target] 一定大于 dp[target]
        return (sum-dp[target]) - dp[target];

        
    }
}

494.目标和

题目链接:https://leetcode.cn/problems/target-sum/

思路:

这道题目咋眼一看和动态规划背包啥的也没啥关系。

本题要如何使表达式结果为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的组合。(核心)

这里的left,就是bagSize,也就是我们后面要求的背包容量。

同时,看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了,例如sum 是5,S是2的话其实就是无解的,所以:

if ((target + sum) % 2 == 1) return 0; // 此时没有方案

同时如果 target的绝对值已经大于sum,那么也是没有方案的。

if (abs(target ) > sum) return 0; // 此时没有方案

因为每个物品(题目中的1)只用一次,所以是一个01背包问题。这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。

动规五部曲:
(1)确定dp数组以及下标含义
dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

(2)确定递归公式
只要搞到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]]

这个公式非常重要,会反复用到!

(3)dp数组初始化
从递推公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递推结果将都是0。

所以本题我们应该初始化 dp[0] 为 1。

(4)确定遍历顺序
对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。

(5)举例推导dp数组
输入:nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下:
在这里插入图片描述

代码:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // left 代表所有取正数的元素  right 代表所有取负数的元素
        // left - right = target && left + right = sum
        // right + target = sum - right = left
        // 2 * left = sum + target =>  left = (sum + target) /2
        int sum = 0;
        for(int i:nums)
            sum += i;
        if(Math.abs(target) > sum || (target + sum) % 2 != 0 ) return 0;
        int left = (sum + target) >> 1;
        // 本题的关键就在于在nums找出和为left的组合
        int[] dp = new int[left+1];
        // 如果不初始化的话,dp累加就会一直为0
        dp[0] = 1;
        for(int i=0; i<nums.length;i++){
            for(int j=left;j>=nums[i];j--)
                // dp[j] 代表数组中若干个元素组合成和为j的方案数
                // 已经有一个1(nums[i]) 的话,有 dp[4]种方法凑成容量为5的背包。
                // 同理 1 ~ 5
                //dp[5] = dp[0] + ... + dp[5] 
                dp[j] = dp[j] + dp[j-nums[i]];
        }
        return dp[left];
    }
}

474.一和零

题目链接:https://leetcode.cn/problems/ones-and-zeroes/description/

思路:

把总共的 0 和 1 的个数视为背包的容量,每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成,这里的目标值是能放进背包的字符串的数量。

动规五部曲:
(1)确定dp数组以及下标含义
dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。

(2)确定递归公式

  • dp[i-1][j][k] 不选择当前考虑的字符串,至少是这个数值
  • dp[i-1][j-当前字符串使用0的个数][k-当前字符串使用1的个数] 选择当前考虑的字符串

(3)dp数组初始化
为了避免分类讨论,通常多设置一行。这里可以认为,第 00个字符串是空串。第 0 行默认初始化为 0。

(4)确定遍历顺序
常规遍历顺序

(5)举例推导dp数组

代码:

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len+1][m+1][n+1];
        for(int i = 1; i<=len;i++){
            // 计算0和1的数量
            int zeroNum = 0, oneNum = 0;
            for (char ch : strs[i-1].toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            for(int j=0; j<= m; j++){
                for(int k=0; k<=n ;k++){
                    // 先保存上一步结果
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j>= zeroNum && k>= oneNum){
                        dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }
}

思考优化空间,因为当前行只参考了上一行的值,因此可以使用「滚动数组」,也可以「从后向前赋值」。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 动规五部曲
        // 1.确定dp含义
        // dp[i][j] 最多有i个0 和 j个1的strs的最大子集的大小为dp[i][j]
        // 2.确定递推公式
        // dp[i][j]可以由前一个strs里的字符串推导出来,当前strs里的字符串有zeroNum个0,oneNum个1
        // dp[i][j] = dp[i-zeroNum][j-oneNum]+1
        int len = strs.length;
        // int[][][] dp = new int[len+1][m+1][n+1];
        int[][] dp = new int[m + 1][n + 1];
        // 计算0和1的数量
        for (String str : strs) {
            int zeroNum = 0, oneNum = 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);
                }
            }
        }
        // for(int i = 1; i<=len;i++){
        // // 计算0和1的数量
        // int zeroNum = 0, oneNum = 0;
        // for (char ch : strs[i-1].toCharArray()) {
        // if (ch == '0') {
        // zeroNum++;
        // } else {
        // oneNum++;
        // }
        // }
        // for(int j=0; j<= m; j++){
        // for(int k=0; k<=n ;k++){
        // // 先保存上一步结果
        // dp[i][j][k] = dp[i-1][j][k];
        // if(j>= zeroNum && k>= oneNum){
        // dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
        // }
        // }
        // }
        // }
        // return dp[len][m][n];

        return dp[m][n];
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/466110.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

阿里巴巴国际站商品采集商品信息抓取API免费测试入口(英文商品信息跨境电商商品信息自动化抓取)

alibaba.item_get 获取商品详情信息 alibaba.item_search 关键字搜索商品列表 进入API测试页&#xff0c;获取key和密钥 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥api_nameString是API接口名称…

Docker学习之使用harbor搭建私有仓库(超详解析)

实验目的&#xff1a; 使用centos7&#xff0c;基于harbor构建私有仓库 实验步骤&#xff1a; 下载相关安装包和依赖&#xff1a; [rootlocalhost ~]# yum install -y yum-utils device-mapper-persistent-data lvm2 wget //安装docker所需要的相关依赖 [rootlocalhost ~]#…

中国休闲装行业深度调研分析

环洋咨询Global Info Research的休闲装市场调研报告提供休闲装市场的基本概况&#xff0c;包括定义&#xff0c;分类&#xff0c;应用和产业链结构&#xff0c;同时还讨论发展政策和计划以及制造流程和成本结构&#xff0c;分析休闲装市场的发展现状与未来市场趋势&#xff0c;…

java入门-变量与常量

java 基本语法-变量与常量 变量 变量的本质 程序中我们会经常看到类似 int x 3**;** 的表达式&#xff0c;x就是我们常说的变量&#xff0c;从计算机角度我们来看看变量x的本质是什么&#xff1f; 在程序开发中定义一个变量x, 计算机会在内存中开辟内存空间&#xff0c;计算…

【C语言基础】:字符函数和字符串函数

文章目录 一、字符函数1. 字符分类函数2. 字符转化函数 二、字符串函数1. strlen函数的使用和模拟实现strlen函数的使用strlen函数的模拟实现 2. strcpy函数的使用和模拟实现strcpy函数的使用strcpy函数的模拟实现 3. strcat函数的使用和模拟实现strcat函数的使用strcat函数的模…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:Grid)

网格容器&#xff0c;由“行”和“列”分割的单元格所组成&#xff0c;通过指定“项目”所在的单元格做出各种各样的布局。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 仅支持GridItem…

MasterAlign视觉对位软件提示系统校准时间错误解决方案

MasterAlign视觉对位软件提示系统校准时间错误解决方案 一、问题现象 当运行软件时弹出“系统校准时间错误”的提示&#xff0c;如下图&#xff1a; 出现“系统校准时间错误”提示&#xff0c;说明当前系统时间比上一次软件运行时的系统时间提前了&#xff0c;需要修改当前系…

Windows系统搭建web网站并结合内网穿透实现公网访问本地站点

文章目录 使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点&#xff0c;测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中&#xff0c;查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2.2 映…

苹果MacOS电脑使用内网穿透轻松远程桌面本地Windows系统电脑

文章目录 1. 测试本地局域网内远程控制1.1 Windows打开远程桌面1.2 局域网远程控制windows 2. 测试Mac公网远程控制windows2.1 在windows电脑上安装cpolar2.2 Mac公网远程windows 3. 配置公网固定TCP地址 日常工作生活中&#xff0c;有时候会涉及到不同设备不同操作系统之间需要…

JetBrains全家桶激活,分享PyCharm 2024 激活的方案

大家好&#xff0c;欢迎来到金榜探云手&#xff01; PyCharm 公司简介 JetBrains 是一家专注于开发工具的软件公司&#xff0c;总部位于捷克。他们以提供强大的集成开发环境&#xff08;IDE&#xff09;而闻名&#xff0c;如 IntelliJ IDEA、PyCharm、和 WebStorm等。这些工具…

RP2040 VSCode C/C++开发环境快速部署

RP2040 VSCode C/C开发环境快速部署 &#x1f4cc;安装参考《树莓派(Raspberry Pi) Pico VSCode C/C开发环境配置(无需Visual Studio)》&#x1f4cd;Windows环境下 MSYS2一键式部署pico程序包&#xff0c;下载地址&#xff1a;https://github.com/raspberrypi/pico-setup-wind…

简单使用NSIS打包软件

NSIS是一个开源的打包工具. 官网: Download - NSIS (sourceforge.io) 使用这个编译 ​ 但是不建议使用这玩意写脚本,字体太难看了.我用vscode写的脚本,用这个编译的. ​ 写好脚本用这个软件打开, 然后选择这个编译,如果语法有错误 会编译不过,会提醒你哪一行不行,如果编译…

探讨NLP对行业大量数据信息抽取的技术实现

在本文中&#xff0c;为了实现高效的信息抽取&#xff0c;我们采用了一个自主研发的多模态AI的大模型NLP平台。 这个平台的使用过程分为以下几个步骤&#xff1a; 数据收集&#xff1a;我们收集了与项目相关的100条数据样本&#xff0c;这些样本涵盖了各种商品描述&#xff0c…

一口气看完明朝276年历史

明朝是中国历史上最后一个由汉人建立的大一统封建王朝&#xff0c;建立于公元1368年&#xff0c;亡于公元1644年&#xff0c;国祚276年&#xff0c;传12世16帝。 太祖建国 太祖&#xff08;1368~1398&#xff09; 公元1368年&#xff0c;朱元璋在南京应天府建元称帝&#xff…

多行业预约小程序源码系统:单多门店一键切换 带完整的安装教程以及安装代码包

在当今数字化时代&#xff0c;小程序以其便捷、高效的特点&#xff0c;成为企业连接用户、提升服务体验的重要工具。下面&#xff0c;罗峰给大家分享一款多行业预约小程序源码系统&#xff0c;该系统支持单多门店一键切换&#xff0c;并附带完整的安装教程及安装代码包&#xf…

【日本語】N2考试湖北报名笔记

阅读资料 视频&#xff1a;JLPT报名技巧 使用浏览器调试模式快速报名&#xff1b; 1 报名流程 【考场选择】 1.1 春季报名&#xff1a;03-19 07:00:00 1.2 预习网站登录信息 1.3 登录验证码&#xff1a;06:55 &#xff08;图片来自视频《教日语的阿飞老师 - 担心能力考抢…

QY-02-W2 无线雨量监测站 防洪防汛 大坝水库雨水情实时监测

无线雨量监测站配置&#xff1a; 不锈钢支架、雨量传感器、太阳能板、数据采集发送器。 产品概述 无线雨量监测站是一款无线传输数据的雨量监测设备&#xff0c;由不锈钢支架、ABS雨量筒、不锈钢防护箱、主机采集器、无线数据发送装置、太阳能电池板、蓄电池等构成&#xff0c…

CSS基础笔记

第一课 CSS&#xff08;层叠式样式表&#xff09;&#xff1b;样式规则由 选择器、 属性 以及 属性值 组成 内联样式表、内嵌样式表、外部样式表 内联样式表 写在标签里 用 style 属性进行表示&#xff0c;优先级比 内嵌 和 外部 高 <h1 style"color: blue; text-…

java8:LinkedList的实现原理

概述 先来看看源码中的这一段注释&#xff0c;我们先尝试从中提取一些信息&#xff1a; Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).All of the operations …

ubuntu下摩尔线程s80配置ai绘图环境

首先我的桌面是gdm,然后安装github上的sdk&#xff0c;重启进不去桌面了 解决方法&#xff1a; 开机以后选ubuntu的高级选项&#xff0c;换旧一点的linux内核&#xff0c;然后卡在进程上&#xff0c;ctrlaltf2斤tty sudo apt remove musa 卸载完驱动就可以进系统了