当前位置: 首页 > news >正文

153、【动态规划】leetcode ——416. 分割等和子集:滚动数组(C++版本)

题目描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
原题链接:1049. 最后一块石头的重量 II

解题思路

本题要找的是最小重量,我们可以将石头划分成两个集合,当两个集合的重量越接近时,相减后,可达到的装量就会是最小,此时本题的思路其实就类似于 416. 分割等和子集(动态规划:二维数组+滚动数组) 。

首先,对所有石头的总重量求和,然后设置一个变量target表示总重量之和的二分之一,使用动态规划的方式,划分出一个集合之和dp[target],然后用总重量之和减去dp[target],就得到对石头的另一个集合划分之和。二者相减,就是最小重量。

  • 动态规划五步曲:

(1)dp[j]含义: 在背包容量为j的条件下,可装入的最大物品重量总和。

(2)递推公式: dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sumNums = 0;for(int i = 0; i < stones.size(); i++)       sumNums += stones[i];int target = sumNums / 2;int dp[1501] = {0};int n = stones.size();for(int i = 0; i < n; i++) {for(int j = target; j >= stones[i]; j--) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return abs(sumNums - dp[target] - dp[target]);}
};

参考文章:1049. 最后一块石头的重量 II

相关文章:

153、【动态规划】leetcode ——416. 分割等和子集:滚动数组(C++版本)

题目描述 原题链接&#xff1a;1049. 最后一块石头的重量 II 解题思路 本题要找的是最小重量&#xff0c;我们可以将石头划分成两个集合&#xff0c;当两个集合的重量越接近时&#xff0c;相减后&#xff0c;可达到的装量就会是最小&#xff0c;此时本题的思路其实就类似于 4…...

linux head命令(head指令)(获取文件或管道输出结果前n行,默认前10行)与sed命令区别

head命令是一个在Linux系统中常用的命令&#xff0c;用于读取文件的前几行&#xff08;默认读取前10行&#xff09; 文章目录使用方法读取文件的前10行&#xff1a;head filename读取文件的前n行&#xff1a;head -n行数 filename读取多个文件的前几行&#xff1a;head -n 行数…...

Mysql数据库09——分组聚合函数

类似pandas里面的groupby函数&#xff0c;SQL里面的GROUP BY子句也是可以达到分组聚合的效果。 常用的聚合函数有COUNT(),SUM(),AVG(),MAX(),MIN()&#xff0c;其用法看名字都看的出来&#xff0c;下面一一介绍 聚合函数 COUNT()计数 统计student表中计科系学生的人数。 SE…...

第43章 菜单实体及其约束规则的定义实现

1 Core.Domain.Security.Menu namespace Core.Domain.Security { /// <summary> /// 【菜单--类】 /// <remarks> /// 摘要&#xff1a; /// 通过该实体类及其属性成员&#xff0c;用于实现当前程序【Core】.【领域】.【安全】.【菜单】实体与“[ShopDemo].[…...

OpenAI最重要的模型【CLIP】

最近的 AI 突破 DALLE和 Stable Diffusion有什么共同点&#xff1f; 它们都使用 CLIP 架构的组件。 因此&#xff0c;如果你想掌握这些模型是如何工作的&#xff0c;了解 CLIP 是先决条件。 此外&#xff0c;CLIP 已被用于在 Unsplash 上索引照片。 但是 CLIP 做了什么&…...

分享112个JS菜单导航,总有一款适合您

分享112个JS菜单导航&#xff0c;总有一款适合您 112个JS菜单导航下载链接&#xff1a;https://pan.baidu.com/s/1Dm73d2snbu15hZErJjTXxg?pwdfz1c 提取码&#xff1a;fz1c Python采集代码下载链接&#xff1a;https://wwgn.lanzoul.com/iKGwb0kye3wj base_url "h…...

MySQL 3:MySQL数据库基本操作 DQL

数据库管理系统的一个重要功能是数据查询。数据查询不应简单地返回数据库中存储的数据&#xff0c;还应根据需要对数据进行过滤&#xff0c;确定数据的显示格式。MySQL 提供了强大而灵活的语句来实现这些操作。MySQL数据库使用select语句查询数据。 select [all|distinct]<…...

sql语句的优化

sql优化 优化数据访问 查询性能低下最基本的原因是访问的数据太多&#xff0c;大部分性能低下的查询都可以通过减少访问的数据量来优化所以关于低效的查询&#xff0c;需要确认是否检索了大量不需要的数据&#xff0c;以及mysql服务器层是否在分析大量不需要的数据 因为有些查…...

Shell脚本之——自动安装JDK

目录 1.修改主机名 2.创建文件&#xff0c;单独存放Shell脚本 3.编写Shell脚本 4.Shell脚本命令简介 (1)文件头 (2)打印命令 (3)设置全局变量 (4)条件判断 (5)解压 (6)文件重命名 (7)在/etc/profile指定行插入 5.完整脚本内容 6.重启环境变量 7.判断java是否配置…...

大数据---Hadoop安装Hadoop简易版

编写自动安装Hadoop的shell脚本 完整流程: 大数据—Hadoop安装教程&#xff08;二&#xff09; 文章目录编写自动安装Hadoop的shell脚本上传压缩包编写shell脚本vim hadoopautoinstall.sh运行上传压缩包 在opt目录下创建连个目录install和soft 将压缩包上传到install目录下 …...

Spring框架中使用到的设计模式以及对应的类(方法)

模板方法--->postProcessBeanFactory&#xff0c;onFresh、initPropertySource装饰器模式--->BeanWrapper委托者模式--->BeanDefinitionParseDelegate策略模式--->ClassPathXmlApplicationContext、FileSystemApplicationContext、XMLBeanDefinitionReader、Proper…...

类和类的定义

6.2 类和类的定义 面向对象最重要的概念就是类&#xff08;Class&#xff09;和实例&#xff08;Instance&#xff09;&#xff0c;必须牢记类是抽象的模板&#xff0c;比如学生类&#xff0c;而实例是根据类创建出来的一个个具体的对象&#xff0c;每个对象都拥有相同的方法&…...

丝绸之路——NFT 系列来袭!

丝绸之路的经历讲述了汉朝时代的一个重要历史事件。该系列中的 NFT 带有中国这段黄金时代令人愉悦的视觉元素&#xff0c;使其成为值得收藏的物品。 NFT 系列介绍 敦煌女神像01&#xff08;左&#xff09;&#xff1b;汉代士兵&#xff08;中&#xff09;&#xff1b;敦煌女神像…...

配置CMAKE编译环境:VSCODE + MinGW

一. MinGW安装 MinGW(Minimalist GNU For Windows)是个精简的Windows平台C/C、ADA及Fortran编译器&#xff0c;相比Cygwin而言&#xff0c;体积要小很多&#xff0c;使用较为方便。 MinGW最大的特点就是编译出来的可执行文件能够独立在Windows上运行。 MinGW的组成&#xff…...

六、mybatis与spring的整合

Spring整合Mybaits的步骤 引入依赖 在Spring整合Mybaits的时候需要引入一个中间依赖包mybatis-spring <dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.5</version> </dependency&g…...

JavaWeb--JDBC

JDBC1 JDBC概述1.1 JDBC概念1.2 JDBC本质1.3 JDBC好处2 JDBC快速入门2.1 编写代码步骤2.2 具体操作3 JDBC API详解3.1 DriverManager3.2 Connection3.2.1 获取执行对象3.2.2 事务管理3.3 Statement3.3.1 概述3.3.2 代码实现3.4 ResultSet3.4.1 概述3.4.2 代码实现3.5 案例3.6 P…...

大数据框架之Hadoop:入门(四)Hadoop运行模式

Hadoop运行模式包括&#xff1a;本地模式、伪分布式模式以及完全分布式模式。 Hadoop官方网站&#xff1a;http://hadoop.apache.org/ 4.1本地运行模式 4.1.1官方Grep案例 1.创建在hadoop文件夹下面创建一个input文件夹 [roothdp101 hadoop]# mkdir input2.将Hadoop的xml配…...

《爆肝整理》保姆级系列教程python接口自动化(十一)--发送post【data】(详解

简介  前面登录的是传 json 参数&#xff0c;由于其登录机制的改变没办法演示&#xff0c;然而在工作中有些登录不是传 json 的&#xff0c;如 jenkins 的登录&#xff0c;这里小编就以jenkins 登录为案例&#xff0c;传 data 参数&#xff0c;给各位童鞋详细演练一下。 一、…...

【微服务】Nacos注册中心

&#x1f6a9;本文已收录至专栏&#xff1a;微服务探索之旅 &#x1f44d;希望您能有所收获 &#x1f44d;Nacos和Eureka一样也可以充当服务的注册中心&#xff0c;让我们一起看看有何区别&#xff1f; 点击跳转&#x1f449;【微服务】Eureka注册中心 &#x1f44d;Nacos除了可…...

跟开发打了半个月后,我终于get报bug的正确姿势了

在测试人员提需求的时候&#xff0c;大家经常会看到&#xff0c;测试员和开发一言不合就上BUG。然后开发一下就炸了&#xff0c;屡试不爽&#xff0c;招招致命。 曾经看到有个段子这么写道&#xff1a; 不要对程序员说&#xff0c;你的代码有BUG。他的第一反应是&#xff1a;…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...