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

2024-05-27 23:44

本文主要是介绍「动态规划」删除并获得点数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

这篇关于「动态规划」删除并获得点数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1008931

相关文章

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T