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

「动态规划」删除并获得点数

力扣原题链接,点击跳转。

给你一个整数数组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]);}
};

相关文章:

「动态规划」删除并获得点数

力扣原题链接&#xff0c;点击跳转。 给你一个整数数组nums。每次操作&#xff0c;可以删除任意一个值n&#xff0c;接着获得点数n&#xff0c;并同时删除所有的n-1和n1。你最多能获取多少点数&#xff1f; 这个问题的解法相当巧妙。我们可以把问题先转化一下。用类似计数排序…...

MongoDB CRUD操作:内嵌文档数组查询

MongoDB 内嵌文档数组查询 文章目录 MongoDB 内嵌文档数组查询查询数组内嵌文档为文档数组中的字段指定查询条件指定文档数组内嵌文档字段的查询条件使用数组索引查询内嵌文档的字段 为文档数组指定多个条件单个内嵌文档满足内嵌字段的多个查询条件符合标准的元素组合 使用 Mon…...

【C++】每日一题 50 Pow(x,n)

实现 pow(x, n) &#xff0c;即计算 x 的整数 n 次幂函数&#xff08;即&#xff0c;x^n &#xff09;。 当需要计算x的n次幂时&#xff0c;可以使用递归或者迭代的方式来实现。 #include <iostream>double myPow(double x, int n) {if (n 0) {return 1.0;} else if (…...

HG/T 6088-2022 透水道路用涂料检测

透水混凝土是指由水泥、矿物掺合料、骨料、外加剂及水等主要材料经拌合形成的&#xff0c;具有透水功能的混凝土材料&#xff0c;用于其表面的涂料称为透水道路用涂料。 HG/T 6088-2022透水道路用涂料检测项目&#xff1a; 测试指标 测试方法 有害物质限量 GB 38468 在容器…...

linux定时清理docker日志脚本

Linux 定时清理 Docker 日志的脚本与配置指南 在使用 Docker 容器化应用程序时,日志文件可能会迅速增长,占用大量磁盘空间。为了保持系统的稳定性和高效运行,定期清理 Docker 日志文件是必要的。本文将介绍如何编写一个 Linux 脚本来清理 Docker 日志文件,并通过 cron 定时…...

ROS学习笔记(16):夹缝循迹

0.前言 在笔记的第15期对巡墙驾驶的原理进行了简单讲解&#xff0c;而这期我们来讲一下夹缝循迹&#xff0c;也常被叫follow the gap&#xff0c;也更新一些概念。 1.探索式路径规划与避障 1.概念 无预先建图的路径规划叫探索式路径规划&#xff0c;例如巡墙循迹和夹缝循迹&…...

【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年设立了农业图书情报系&#xff0c;1993 年农业图书情报系更名为信息管理系&#xff0c;本科专业名称也于1999年更名为信息管理与信息系统专业。1994年计算中心开始招收计算机应用专…...

利用java8 的 CompletableFuture 优化 Flink 程序,性能提升 50%

你好&#xff0c;我是 shengjk1&#xff0c;多年大厂经验&#xff0c;努力构建 通俗易懂的、好玩的编程语言教程。 欢迎关注&#xff01;你会有如下收益&#xff1a; 了解大厂经验拥有和大厂相匹配的技术等 希望看什么&#xff0c;评论或者私信告诉我&#xff01; 文章目录 一…...

香橙派 AIpro综合体验及AI样例运行

香橙派 AIpro综合体验及AI样例运行 环境&#xff1a; 香橙派版本&#xff1a; AIpro(8TOPSINT8) OS : Ubuntu 22.04.3 LTS(GNU/Linux 5.10.0 aarch64) (2024-03-18) 远程服务端1&#xff1a;OpenSSH 8.9p1 远程服务端2&#xff1a;TightVNC Server 1.3.10 远程客户端&#xf…...

通过域名接口申请免费的ssl多域名证书

来此加密已顺利接入阿里云的域名接口&#xff0c;用户只需一键调用&#xff0c;便可轻松完成域名验证&#xff0c;从而更高效地申请证书。接下来&#xff0c;让我们详细解读一下整个操作过程。 来此加密官网 免费申请SSL证书 免费SSL多域名证书&#xff0c;泛域名证书。 首先&a…...

【JAVA WEB实用与优化技巧】如何自己封装一个自定义UI的Swagger组件,包含Swagger如何处理JWT无状态鉴权自动TOKEN获取

目录 一、Swagger 简介1. 什么是 Swagger&#xff1f;2. 如何使用 Swagger3. Springboot 中swagger的使用示例1. maven 引入安装2. java配置 二、Swagger UI存在的缺点1.不够方便直观2.请求的参数没有缓存3.不够美观4.如果是JWT 无状态登录&#xff0c;Swagger使用起来就没有那…...

理解大语言模型(二)——从零开始实现GPT-2

相关说明 这篇文章的大部分内容参考自我的新书《解构大语言模型&#xff1a;从线性回归到通用人工智能》&#xff0c;欢迎有兴趣的读者多多支持。 本文涉及到的代码链接如下&#xff1a;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! 翻译过来就是 警告&#xff1a;远程主机标识已更改&#xff01; 此报错是由于远程的…...

工业级3D开发引擎HOOPS:创新与效率的融合!

在当今这个技术日新月异的时代&#xff0c;3D技术已成为推动各行各业发展的重要力量。从工程设计到游戏开发&#xff0c;从虚拟现实到增强现实&#xff0c;3D技术的应用无处不在&#xff0c;它极大地丰富了我们的生活和工作。而在这样的背景下&#xff0c;HOOPS作为一个强大的3…...

IDEA创建Spring Boot项目

1 打开新建项目界面 如图1&#xff0c;打开IDEA&#xff0c;点击菜单栏的File->New->Project&#xff0c;打开新建项目界面。 图1 新建项目 2 填写项目信息 在新建项目界面点击左侧工具栏的Spring Initializr选项&#xff0c;进行Spring Boot项目信息的填写&#xff…...

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之间的区别

探索演进&#xff1a;了解IPv4和IPv6之间的区别 在广阔的互联网领域中&#xff0c;设备之间的通信依赖于一组独特的协议来促进连接。前景协议中&#xff0c;IPv4&#xff08;Internet 协议版本 4&#xff09;和 IPv6&#xff08;Internet 协议版本 6&#xff09;是数字基础设施…...

Python 实现Word (DOC或DOCX)与TXT文本格式互转

目录 引言 安装Python库 使用Python将Word转换为TXT文本格式 使用Python将TXT文本格式转换为Word 引言 Word文档和TXT文本文件是日常工作和生活中两种常见的文件格式&#xff0c;各有其特点和优势。Word文档能够保留丰富的格式设置&#xff0c;如字体、段落、表格、图片等…...

anaconda install on CentOS 7

参考&#xff1a; CentOS 7安装conda并配置环境 CentOS 7安装conda并配置环境_centos conda-CSDN博客...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

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

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

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

VSCode 使用CMake 构建 Qt 5 窗口程序

首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...