当前位置: 首页 > 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;…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...