「动态规划」如何计算能获得多少点数?

740. 删除并获得点数icon-default.png?t=N7T8https://leetcode.cn/problems/delete-and-earn/description/

给你一个整数数组nums,你可以对它进行一些操作。每次操作中,选择任意一个nums[i],删除它并获得nums[i]的点数。之后,你必须删除所有等于nums[i] - 1和nums[i] + 1的元素。开始你拥有0个点数。返回你能通过这些操作获得的最大点数。

  1. 输入:nums = [3,4,2],输出:6,解释:删除4获得4个点数,因此3也被删除。之后,删除2获得2个点数。总共获得6个点数。
  2. 输入:nums = [2,2,3,3,3,4],输出:9,解释:删除3获得3个点数,接着要删除两个2和4。之后,再次删除3获得3个点数,再次删除3获得3个点数。总共获得9个点数。

提示:1 <= nums.length <= 2 * 10^4,1 <= nums[i] <= 10^4。


我们用类似计数排序的思想。定义一个数组arr,arr[i]表示:在nums中,所有点数i的和。如,如果nums = [2,2,3,3,3,4],那么nums = [0,0,4,9,4],意思是:0出现0次,和为0;1出现0次,和为0;2出现2次,和为4;3出现3次,和为9;4出现1次,和为4。

那么,问题就转化为:在nums中选择一些元素,让这些元素的和最大。你不能选择相邻的元素。咦,咋这么眼熟?这不就是打家劫舍嘛!看来小偷又改行来玩游戏了,嘿嘿。我们用动态规划的思想来解决这个问题。

确定状态表示:根据经验和题目要求,我们用dp[i]表示:选到i位置的元素后,此时的最大和。再细分为:

  • 用f[i]表示:必须选择i位置的元素后,此时的最大和
  • 用g[i]表示:不能选择i位置的元素后,此时的最大和

推导状态转移方程:分别讨论2种情况中,最近的一步,即是否选择i - 1位置的元素。

  • 考虑f[i]。如果选择i位置的元素,那么就不能选择i - 1位置的元素。选择完i位置的元素之后的最大和,就等于不能选择i - 1位置的元素之后的最大和加上i位置的元素,即f[i] = g[i - 1] + arr[i]。
  • 考虑g[i]。如果不能选择i位置的元素,那么此时的最大和就等于考虑完i - 1元素之后的最大和。由于不确定是否选择i - 1位置的元素,所以不能选择i位置的元素后的最大和,就等于是否选择i - 1位置的元素这2种情况的最大和的较大值,即g[i] = max(f[i - 1], g[i - 1])。

综上所述:f[i] = g[i - 1] + arr[i],g[i] = max(f[i - 1], g[i - 1])

初始化:根据状态转移方程,在计算f[0]和g[0]时会越界,所以要对其初始化。

  • f[0]表示:必须选择0位置的元素之后,此时的最大和,显然f[0] = arr[0]。
  • g[0]表示:不能选择0位置的元素之后,此时的最大和,显然g[0] = 0。

综上所述:f[0] = arr[0],g[0] = 0

填表顺序:根据状态转移方程,f[i]依赖于g[i - 1],g[i]依赖于f[i - 1]和g[i - 1],所以应从左往右同时填f表和g表

返回值:假设arr数组有n个元素。最终要返回考虑完n - 1位置的元素后,此时的最大和。由于并不确定是否选择n - 1位置的元素,再根据状态表示,我们应返回的是,是否选择n - 1位置的元素这2种情况中,最大和的较大值,即max(f[n - 1], g[n - 1])

细节问题:由于f表和g表的下标范围是[0, n - 1],所以规模都是1 x n

时间复杂度:O(N),空间复杂度:O(N)。

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10001;

        // 转化问题
        vector<int> arr(N);
        for (auto num : nums) {
            arr[num] += num;
        }

        // 创建dp表
        vector<int> f(N);
        auto g = f;

        // 初始化
        f[0] = arr[0];

        // 填表
        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]);
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/695809.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【网络安全的神秘世界】web应用程序安全与风险

&#x1f31d;博客主页&#xff1a;泥菩萨 &#x1f496;专栏&#xff1a;Linux探索之旅 | 网络安全的神秘世界 | 专接本 第一章&#xff1a;web应用程序安全与风险 web攻击基础知识 1、什么是web应用攻击 web攻击的本质&#xff0c;就是通过http协议篡改应用程序&#xff0…

虚拟机ping不通主机,但是主机可以ping通虚拟机

我在Windows10系统安装了虚拟机&#xff0c;设置的主机与虚拟机的连接方式是桥接&#xff0c;安装好后&#xff0c;发现虚拟机ping不通主机&#xff0c;但是主机可以ping通虚拟机。 我的操作是&#xff1a;关闭防火墙&#xff0c;发现虚拟机可以ping通主机了。说明是Windows10…

python后端结合uniapp与uview组件tabs,实现自定义导航按钮与小标签颜色控制

实现效果&#xff08;红框内&#xff09;&#xff1a; 后端api如下&#xff1a; task_api.route(/user/task/states_list, methods[POST, GET]) visitor_token_required def task_states(user):name_list [待接单, 设计中, 交付中, 已完成, 全部]data []color [#F04864, …

CPP初级:模板的运用!

目录 一.泛型编程 二.函数模板 1.函数模板概念 2.函数模板格式 3.函数模板的原理 三.函数模板的实例化 1.隐式实例化 2.显式实例化 3.模板参数的匹配原则 四.类模板 1.类模板的定义格式 2.类模板的实例化 一.泛型编程 泛型编程&#xff1a;编写与类型无关的通用代码…

express入门01服务器搭建以及get和post请求的监听

微搭提供了后端API的能力&#xff0c;但是不同的版本收费差别巨大&#xff0c;因为使用的门槛限制了中小企业使用低代码平台。那可不可以既要又要呢&#xff1f;答案是肯定的&#xff0c;那其实掌握一定的后端框架&#xff0c;借助我们在低代码中已经熟练掌握的技能其实是比较容…

2024.6.9 七

Python的time库 先导入库 import time相关函数 time.time() 返回当前时间的时间戳(一个记录时间的浮点数),从1970年开始算的 time.localtime(sec) 返回一个指定时间戳(sec)的struct_time对象,是一个元组封装起来的,默认是当地时间 struct_time对象 tm_year 年 tm_mon 月 tm_…

CDR2024软件破解Keygen激活工具2024最新版

CorelDRAW Graphics Suite2024最新版&#xff0c;这是一款让我爱不释手的图形设计神器&#xff01;作为一个软件评测专家&#xff0c;我一直在寻找一款能够提升我的设计效率和创造力的工具。而这款软件&#xff0c;简直就是为我量身定制的&#xff01;&#x1f389; 「CorelDR…

算法金 | AI 基石,无处不在的朴素贝叶斯算法

大侠幸会&#xff0c;在下全网同名「算法金」 0 基础转 AI 上岸&#xff0c;多个算法赛 Top 「日更万日&#xff0c;让更多人享受智能乐趣」 历史上&#xff0c;许多杰出人才在他们有生之年默默无闻&#xff0c; 却在逝世后被人们广泛追忆和崇拜。 18世纪的数学家托马斯贝叶斯…

温度传感器十大品牌

温度传感器品牌排行榜-十大热电偶品牌-热敏电阻品牌排行-Maigoo品牌榜

TikTok Shop账号需要防关联吗?

在TikTokShop作为新兴的电商销售渠道中&#xff0c;保护账号的安全和隐私&#xff0c;防止账号关联成为了重要的任务。为了更好地理解为何需要防关联以及如何进行防范&#xff0c;让我们深入探讨一下这个问题。 为什么要防关联&#xff1f; 1. 账号异常风险&#xff1a;防关联…

电容十大品牌供应商

十大电容器品牌&#xff0c;电解电容-陶瓷电容-超级电容器品牌排行榜-Maigoo品牌榜

Android gradle kts 8.0以上版本配置签名和修改APK输出名字

目录 概述修改签名配置新建签名文件目录配置签名信息使用签名信息打包 修改APK名称 概述 之前写过一篇文章是通过Kotlin的Dsl结合gradle编写的插件来管理项目依赖&#xff0c;我是从一个开源项目叫DanDanPlayAndroid项目上学到的&#xff0c;那时还没有使用toml文件来管理项目…

Linux入门学习(2)

1.相关复习新的指令学习 &#xff08;1&#xff09;我们需要自己创建一个用户&#xff0c;这个用户前期可以是一个root用户&#xff0c;后期使用创建的普通用户 &#xff08;2&#xff09;文件等于文件内容加上文件属性,对于文件的操作就包括对于文件内容的操作和文件属性&…

Apache SeaTunnel社区5月月报更新!

各位热爱 SeaTunnel 的小伙伴们&#xff0c;社区 5 月份月报来啦&#xff01; SeaTunnel 正在迅猛发展&#xff0c;积极投入社区项目建设的小伙伴将促进SeaTunnel不断提升数据同步的高可扩展性、高性能及高可靠性。欢迎关注每月月报更新&#xff0c;期待在下个月的Merge Star月…

Redis持久化说明

Redis的持久化是指将内存中的数据持久化到磁盘中&#xff0c;以保证数据在重启或宕机后不会丢失。 Redis提供了两种主要的持久化方式&#xff1a;RDB(Redis DataBase)和AOF(Append Only File)。 RDB&#xff08;Redis DataBase&#xff09; 1、RDB快照原理 RDB持久化方式会定…

STM32 | 独立看门狗 | RTC(实时时钟)

01、独立看门狗概述 在由单片机构成的微型计算机系统中,由于单片机的工作常常会受到来自外界电磁场的干扰,造成程序的跑飞,而陷入死循环,程序的正常运行被打断,由单片机控制的系统无法继续工作,会造成整个系统的陷入停滞状态,发生不可预料的后果,所以出于对单片机运行状…

ffmpeg视频解码原理和实战-(5)硬件加速解码后进行渲染并输出帧率

头文件&#xff1a; xvideoview.h #ifndef XVIDEO_VIEW_H #define XVIDEO_VIEW_H #include <mutex> #include <fstream> struct AVFrame;void MSleep(unsigned int ms);//获取当前时间戳 毫秒 long long NowMs();/// 视频渲染接口类 /// 隐藏SDL实现 /// 渲染方案…

初阶 《函数》 4. 函数的调用

4. 函数的调用 4.1 传值调用 函数的形参和实参分别占有不同内存块&#xff0c;对形参的修改不会影响实参 4.2 传址调用 传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式 这种传参方式可以让函数和函数外边的变量建立起真正的联系&#xff0c;也就是…

电脑上的瑞士军刀

一、简介 1、一款专为 Windows 操作系统设计的桌面管理工具&#xff0c;它具备保存和恢复桌面图标位置的功能&#xff0c;使用户能够在各种情况下&#xff0c;如分辨率变动、系统更新或其他原因导致的图标位置混乱后&#xff0c;快速恢复到熟悉的工作环境。它还拥有诸多实用功能…

大数据数仓的数据回溯

在大数据领域&#xff0c;数据回溯是一项至关重要的任务&#xff0c;它涉及到对历史数据的重新处理以确保数据的准确性和一致性。 数据回溯的定义与重要性 数据回溯&#xff0c;也称为数据补全&#xff0c;是指在数据模型迭代或新模型上线后&#xff0c;对历史数据进行重新处理…