首页 > 其他分享 >「动态规划」删除并获得点数

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

时间:2024-05-27 21:31:36浏览次数:21  
标签:arr 删除 nums max 元素 数组 点数 动态

力扣原题链接,点击跳转

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

标签:arr,删除,nums,max,元素,数组,点数,动态
From: https://blog.csdn.net/xiang_bolin/article/details/139247873

相关文章

  • 算法导论,矩阵链乘法(动态规划)
    直入主题,5.27学的矩阵链相乘(动态规划)题目理解:        1.原题                要求:对A1,A2,A3......An进行矩阵的乘法(线性代数的基础知识),求通过添加括号,以达到的最小乘法次数    2.题目理解        乘法:由于矩阵乘法的结合......
  • Linux如何在目录下灵活创建、浏览、删除百万个文件
    目录一、创建百万级小文件1、单核CPU情况2、多核CPU情况3、执行效率对比3.1、单核的顺序执行3.2、多核的并发执行二、如何列出/浏览这些文件1、查看目录下文件的数量2、列出?3、ls-f(关闭排序功能)3.1、执行效率对比4、通过重定向导入到文件中浏览对应的文件名三、如何快速删除目录......
  • 一键恢复,U盘被删除文件方法分享
    U盘是一种轻巧便携的移动储存工具,在日常的工作以及学习过程中,我们经常性会使用它来传输、备份、存储一些重要文件。然而,随着后期使用频率的增多,会在不同的设备上来回插拔,也就给里面存储文件带来了很大的隐患。比方说:在使用的过程中,无意删除了一些重要性很高的文件。那么,怎么恢......
  • vue2+uni-app的实现的动态数据显示
     1:所用技术:Vue2.X,Uview2.0,确保项目上已经安装了Vue2.X 版本和组件Uview(注:其余组件:如ElementUI组件也适用,主要是样式的区别)2:template层<template> <viewclass="NavPage"> <viewclass="LoginCard"> <uni-cardis-shadow:trueclass="CardLogin"......
  • 动态规划--图论中使实用场景概述
    目录一 动态规划概述二 动态规划在图论中应用场景三c实例1.**最短路径问题(Dijkstra算法)**:2.**最小生成树问题(Kruskal算法)**:一 动态规划概述动态规划(DynamicProgramming,简称DP)是一种用于解决具有重叠子问题和最优子结构特性的问题的优化方法。动态规划通过将原......
  • C# 在Excel中添加、应用或删除筛选器 (日期筛选、文本筛选、数字筛选)
    自动筛选器是Excel中的一个基本但极其有用的功能,它可以让你根据特定的条件来自动隐藏和显示你的数据。当有大量的数据需要处理时,这个功能可以帮你快速找到你需要的信息,从未更加有效地分析和处理相关数据。下面将介绍如何使用免费.NETExcel库在Excel中添加、应用和删除自动筛选......
  • 京东云5月产品动态
    1.【智算服务】新品上线智算平台GCS是面向AI创业公司和AI从业者的AI算力生命周期管理和AI应用生命周期管理平台。平台提供高性价比算力资源,以及基于大模型的AI应用生态市场。提供全网低价算力、帮您快速上手AIGC应用。2.【节能宝PUE】新品上线节能宝(PUE优化),是一款京东云面向......
  • EXSI主机自动创建快照,删除快照
    1.开启EXSI主机SSH2.使用SSH连接EXSI主机SSH连接账号密码为登录EXSI主机时的账号密码esxi重启会删除/vmfs/volumes目录外的文件,所以脚本放在/vmfs/volumes/datastore1进入数据存储目录下,这个名称根据自己建立数据存储的名称来cd/vmfs/volumes/datastore1/创建存放脚......
  • 静态库与动态库
    文章目录参考文章一、什么是库1.命名规则2.Linux下生成静态库的步骤3.静态库的使用4.静态库制作举例1.源码2.静态库的制作3.静态库的使用三、动态库1.命名规则2.Linux下生成动态库的步骤3.动态库的使用4.动态库的制作举例1.动态库的制作2.动态库的使用3.解决动态库无法......
  • 链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
    7-4sdut-C语言实验-单链表中重复元素的删除分数20全屏浏览切换布局作者 马新娟单位 山东理工大学按照数据输入的相反顺序(逆位序)建立一个单链表,并将单链表中重复的元素删除(值相同的元素只保留最后输入的一个)。输入格式:第一行输入元素个数n(1<=n<=15);第二......