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

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

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

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

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...