「动态规划」删除并获得点数
力扣原题链接,点击跳转。
给你一个整数数组nums。每次操作,可以删除任意一个值n,接着获得点数n,并同时删除所有的n-1和n+1。你最多能获取多少点数?
这个问题的解法相当巧妙。我们可以把问题先转化一下。用类似计数排序的思路,定义一个数组arr,用arr[i]表示所有的点数i的和。比如nums数组:1、2、2、3、3、3,那么arr数组:0、1、4、9,因为1出现1次,和为1;2出现2次,和为2×2=4;3出现3次,和为3×3=9。
盯着这个arr数组,问题就转化为:在arr数组中选取一个子数组,不能同时选取相邻的元素,请找出一个子数组,让这个子数组所有元素的和最大。如果你看到这里,觉得这道题跟某一道经典问题很像,有这种感觉就对了。具体请看我的另一篇博客:「动态规划」打家劫舍,点击跳转。有了打家劫舍的铺垫,这个问题就非常简单了,思路可以说是一模一样。
用动态规划的思路来解决这个问题。首先确定状态表示,用f[i]表示选到下标为i的元素时,必须选择下标为i的元素,子数组的最大和;用g[i]表示选到下标为i的元素时,不能选择下标为i的元素,子数组的最大和。接着推导状态转移方程,显然f[i]=g[i-1]+arr[i],g[i]=max(f[i-1],g[i-1])。初始化f[0]=arr[0]=0,g[0]=0。为什么arr[0]=0呢?因为点数0不管选多少,和都是0。填表时应从左往右同时填表。arr有n个元素,最后返回max(f[n-1],g[n-1])。
class Solution
{
public:int deleteAndEarn(vector<int>& nums){const int N = 10001;// 用arr[i]表示所有点数i的和vector<int> arr(N);for (auto num : nums)arr[num] += num;// 创建dp表vector<int> f(N);auto g = f;// 填表for (int i = 1; i < N; i++){f[i] = g[i - 1] + arr[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[N - 1], g[N - 1]);}
};相关文章:
「动态规划」删除并获得点数
力扣原题链接,点击跳转。 给你一个整数数组nums。每次操作,可以删除任意一个值n,接着获得点数n,并同时删除所有的n-1和n1。你最多能获取多少点数? 这个问题的解法相当巧妙。我们可以把问题先转化一下。用类似计数排序…...
MongoDB CRUD操作:内嵌文档数组查询
MongoDB 内嵌文档数组查询 文章目录 MongoDB 内嵌文档数组查询查询数组内嵌文档为文档数组中的字段指定查询条件指定文档数组内嵌文档字段的查询条件使用数组索引查询内嵌文档的字段 为文档数组指定多个条件单个内嵌文档满足内嵌字段的多个查询条件符合标准的元素组合 使用 Mon…...
【C++】每日一题 50 Pow(x,n)
实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,x^n )。 当需要计算x的n次幂时,可以使用递归或者迭代的方式来实现。 #include <iostream>double myPow(double x, int n) {if (n 0) {return 1.0;} else if (…...
HG/T 6088-2022 透水道路用涂料检测
透水混凝土是指由水泥、矿物掺合料、骨料、外加剂及水等主要材料经拌合形成的,具有透水功能的混凝土材料,用于其表面的涂料称为透水道路用涂料。 HG/T 6088-2022透水道路用涂料检测项目: 测试指标 测试方法 有害物质限量 GB 38468 在容器…...
linux定时清理docker日志脚本
Linux 定时清理 Docker 日志的脚本与配置指南 在使用 Docker 容器化应用程序时,日志文件可能会迅速增长,占用大量磁盘空间。为了保持系统的稳定性和高效运行,定期清理 Docker 日志文件是必要的。本文将介绍如何编写一个 Linux 脚本来清理 Docker 日志文件,并通过 cron 定时…...
ROS学习笔记(16):夹缝循迹
0.前言 在笔记的第15期对巡墙驾驶的原理进行了简单讲解,而这期我们来讲一下夹缝循迹,也常被叫follow the gap,也更新一些概念。 1.探索式路径规划与避障 1.概念 无预先建图的路径规划叫探索式路径规划,例如巡墙循迹和夹缝循迹&…...
【MySQL精通之路】SQL语句(3)-锁和事务语句
目录 1.START TRANSACTION、COMMIT和ROLLBACK语句 2.无法回滚的语句 3.导致隐含COMMIT的语句 4.SAVEPOINT、ROLLBACK TO SAVEPOINT和RELEASE SAVEPOINT语句 5.LOCK INSTANCE FOR BACKUP和UNLOCK INSTANCE语句 6.LOCK TABLE和UNLOCK TABLES语句 6.1 表锁获取 6.2 表锁释放…...
211大学计算机专业不考408,新增的交叉专业却考408!南京农业大学计算机考研考情分析!
南京农业大学信息科技学院可追溯至1981年成立的计算中心和1985年筹建的农业图书情报专业。1987年设立了农业图书情报系,1993 年农业图书情报系更名为信息管理系,本科专业名称也于1999年更名为信息管理与信息系统专业。1994年计算中心开始招收计算机应用专…...
利用java8 的 CompletableFuture 优化 Flink 程序,性能提升 50%
你好,我是 shengjk1,多年大厂经验,努力构建 通俗易懂的、好玩的编程语言教程。 欢迎关注!你会有如下收益: 了解大厂经验拥有和大厂相匹配的技术等 希望看什么,评论或者私信告诉我! 文章目录 一…...
香橙派 AIpro综合体验及AI样例运行
香橙派 AIpro综合体验及AI样例运行 环境: 香橙派版本: AIpro(8TOPSINT8) OS : Ubuntu 22.04.3 LTS(GNU/Linux 5.10.0 aarch64) (2024-03-18) 远程服务端1:OpenSSH 8.9p1 远程服务端2:TightVNC Server 1.3.10 远程客户端…...
通过域名接口申请免费的ssl多域名证书
来此加密已顺利接入阿里云的域名接口,用户只需一键调用,便可轻松完成域名验证,从而更高效地申请证书。接下来,让我们详细解读一下整个操作过程。 来此加密官网 免费申请SSL证书 免费SSL多域名证书,泛域名证书。 首先&a…...
【JAVA WEB实用与优化技巧】如何自己封装一个自定义UI的Swagger组件,包含Swagger如何处理JWT无状态鉴权自动TOKEN获取
目录 一、Swagger 简介1. 什么是 Swagger?2. 如何使用 Swagger3. Springboot 中swagger的使用示例1. maven 引入安装2. java配置 二、Swagger UI存在的缺点1.不够方便直观2.请求的参数没有缓存3.不够美观4.如果是JWT 无状态登录,Swagger使用起来就没有那…...
理解大语言模型(二)——从零开始实现GPT-2
相关说明 这篇文章的大部分内容参考自我的新书《解构大语言模型:从线性回归到通用人工智能》,欢迎有兴趣的读者多多支持。 本文涉及到的代码链接如下:regression2chatgpt/ch11_llm/char_gpt.ipynb1 本文将讨论如何利用PyTorch从零开始搭建G…...
SSH远程登录时常见问题解决
SSH时出现WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! 问题解决——SSH时出现WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! 翻译过来就是 警告:远程主机标识已更改! 此报错是由于远程的…...
工业级3D开发引擎HOOPS:创新与效率的融合!
在当今这个技术日新月异的时代,3D技术已成为推动各行各业发展的重要力量。从工程设计到游戏开发,从虚拟现实到增强现实,3D技术的应用无处不在,它极大地丰富了我们的生活和工作。而在这样的背景下,HOOPS作为一个强大的3…...
IDEA创建Spring Boot项目
1 打开新建项目界面 如图1,打开IDEA,点击菜单栏的File->New->Project,打开新建项目界面。 图1 新建项目 2 填写项目信息 在新建项目界面点击左侧工具栏的Spring Initializr选项,进行Spring Boot项目信息的填写ÿ…...
mysql实战——xtrabackup全量备份/增量备份及恢复
一、测试前准备 mysql数据库 端口3306数据文件目录 /data/mysql/3306/data 安装目录/usr/lcoal/mysql配置文件/etc/my.cnf 创建数据库 testXtra 创建备份目录 备份目录/data/backup/备份恢复数据文件目录/data/mysql/3307/data备份恢复配置文件/etc/my_3307.cnf 二、开始…...
探索演进:了解IPv4和IPv6之间的区别
探索演进:了解IPv4和IPv6之间的区别 在广阔的互联网领域中,设备之间的通信依赖于一组独特的协议来促进连接。前景协议中,IPv4(Internet 协议版本 4)和 IPv6(Internet 协议版本 6)是数字基础设施…...
Python 实现Word (DOC或DOCX)与TXT文本格式互转
目录 引言 安装Python库 使用Python将Word转换为TXT文本格式 使用Python将TXT文本格式转换为Word 引言 Word文档和TXT文本文件是日常工作和生活中两种常见的文件格式,各有其特点和优势。Word文档能够保留丰富的格式设置,如字体、段落、表格、图片等…...
anaconda install on CentOS 7
参考: CentOS 7安装conda并配置环境 CentOS 7安装conda并配置环境_centos conda-CSDN博客...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
