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

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

【学习记录】使用 Kali Linux 与 Hashcat 进行 WiFi 安全分析:合法的安全测试指南

文章目录 &#x1f4cc; 前言&#x1f9f0; 一、前期准备✅ 安装 Kali Linux✅ 获取支持监听模式的无线网卡 &#x1f6e0; 二、使用 Kali Linux 进行 WiFi 安全测试步骤 1&#xff1a;插入无线网卡并确认识别步骤 2&#xff1a;开启监听模式步骤 3&#xff1a;扫描附近的 WiFi…...