简单多状态dp问题----删除并获得点数

740. 删除并获得点数 - 力扣(LeetCode)

本题就是表示不能选值相邻的两个数。 

假设nums = [ 1,2,3,4,5,6],那么这其实就类似一个打家劫舍问题:

即选1,就不能选2,只能选3,4,5,6。

选2,就不能选1,3,只能选4,5,6。

那么显然:如果选1,最大结果为:1 + 3 + 5

如果选2,最大结果为2 + 4 + 6

但是实际的nums肯定不是一堆连续的数

如:nums = [ 1,1,3,4,4,5,8,8,8]

那么此时我们需要将这个nums数组作预处理:

创建一个arr数组,用来统计每个数出现的总和。

如arr[9],arr[0] 表示:0出现的总和 = 0。

arr[1]表示1出现的总和 = 2,同理arr[8] = 24。

则此时arr:

val:0  2  0  3  8  5  0  0  24

arr:0  1  2  3  4  5  6  7  8

那么此时,本题就转换为对arr数组作打家劫舍问题了。

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001;int arr[N] = {0};for(auto x :nums) arr[x] += x;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.rhkb.cn/news/272372.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

excel常用操作备忘

目录 快捷键基础数据透视图统计某列的值出现的频数 数据有效性数据分列运算符顺序文本匹配中的通配符错误的类型&#xff08;常与IF嵌套使用&#xff09;函数RANK(num, ref, [order])MID(str, start, len)逻辑函数混合函数选取整列AVERAGEIF(range, criteria, average_range)TR…

Flink 学习3 - 流处理API的基本转换算子 + 多流转换算子

流处理API-Transform 1、基本转换算子 map、flatMap、filter通常被统一称为基本转换算子&#xff08;简单转换算子&#xff09; DataStream 里没有 reduce 和 sum 这类聚合操作的方法&#xff0c;因为 Flink 设计中&#xff0c;所有数据必须先分组才能做聚合操作。 先 keyB…

ASUS华硕天选2锐龙版笔记本电脑FA506ICB/FA706IC原装出厂Windows11系统,预装OEM系统恢复安装开箱状态

链接&#xff1a;https://pan.baidu.com/s/122iHHEOtNUu4azhVPnxNuA?pwdsqk7 提取码&#xff1a;sqk7 适用型号&#xff1a; FA506IM、FA506IE、FA506IC、FA506IHR FA506IR、FA506IHRB、FA506ICB、FA506IEB FA706IM、FA706IE、FA706IC、FA706IHR FA706IR、FA706IHRB、F…

《Effective Modern C++》- 极精简版 15-21条

本文章属于专栏《业界Cpp进阶建议整理》 继续上篇《Effective Modern C》- 极精简版 5-14条。本文列出《Effective Modern C》的15-21条的个人理解的极精简版本。 Item15、尽量使用constexpr constexpr形容对象 constexpr对象都是const&#xff0c;但是const对象不一定是conste…

单数码管(arduino)

1.连接方法 挨个点亮每个灯 #include <Arduino.h>int pin_list[] {4, 5, 19, 21, 22, 2, 15, 18}; int num_pins sizeof(pin_list) / sizeof(pin_list[0]); // 计算数组中的元素数量void setup() {// 设置每个引脚为输出for(int i 0; i < num_pins; i) {pinMode(p…

ArcGIS学习(十三)多源数据下的城市街道功能评估

ArcGIS学习(十三)多源数据下的城市街道功能评估 本任务带来的内容是多元数据下的城市街道功能评估。本任务包括两个关卡: 城市街道空间中观解读 城市街道功能详细评价 首先,我们来看看本任务的分析思路。 1.城市街道空间中观解读 下面我们正式进入第一关的内容一- 城市…

html--心花怒放

代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>Canvas 绘制一个❤</title><link rel"shortcut icon" href"../../assets/images/icon/favicon.ico" type"ima…

c#触发事件

Demo1 触发事件 <Window x:Class"WPFExample.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"Title"WPF Example" Height"600" Wi…

混合输入矩阵乘法的性能优化

作者 | Manish Gupta OneFlow编译 翻译&#xff5c;宛子琳、杨婷 AI驱动的技术正逐渐融入人们日常生活的各个角落&#xff0c;有望提高人们获取知识的能力&#xff0c;并提升整体生产效率。语言大模型&#xff08;LLM&#xff09;正是这些应用的核心。LLM对内存的需求很高&…

外包干了30天,技术明显退步。。

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 这次来聊一个大家可能也比较关心的问题&#xff0c;那就是就业城市选择的问题。而谈到这个问题&a…

在Mac上安装nginx+rtmp 本地服务器

需要使用终端命令&#xff0c;如果没有Homebrew&#xff0c;要安装Homebrew,执行&#xff1a; ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" 一、安装Nginx 1、先clone Nginx项目到本地&#xff1a; brew tap de…

redis缓存满了的话会发生什么?

线上问题 未及时加监控&#xff0c;导致线上redis被逐出&#xff0c;业务有损 示例&#xff1a; 一个key临时存储在redis等缓存中&#xff0c;如果该key在一段时间内有很大作用 比如一次业务请求&#xff0c;上游服务写入一个value&#xff0c;时长1小时&#xff0c;下游服务…

LiveNVR监控流媒体Onvif/RTSP功能-视频广场点击在线或离线时展示状态记录快速查看通道离线原因

LiveNVR视频广场点击在线或离线时展示状态记录快速查看通道离线原因 1、状态记录1.1、点击在线查看1.2、点击离线查看 2、RTSP/HLS/FLV/RTMP拉流Onvif流媒体服务 1、状态记录 1.1、点击在线查看 可以点击视频广场页面中&#xff0c; 在线 两个字查看状态记录 1.2、点击离线查…

CraxsRat7.4 安卓手机远程管理软件

CRAXSRAT 7.4 最新视频 https://v.douyin.com/iFjrw2aD/ 官方网站下载 http://craxsrat.cn/ 不要问我是谁&#xff0c;我是活雷锋。 http://craxsrat.cn/ CraxsRat CraxsRat7 CraxsRat7.1 CraxsRat7.2 CraxsRat7.3 CraxsRat7.4

SSL 证书,了解一下常识

公司的网站、应用怎么才能保证在互联网上安全运行&#xff0c;不被攻击、盗取数据呢&#xff1f; 创业必经之路&#xff0c;一步一步走就对了&#xff0c;可能没赶上红利期&#xff0c;但不做就等于0。 概述 SSL 证书&#xff08;SSL Certificates&#xff09;又称数字证书&am…

低密度奇偶校验码LDPC(九)——QC-LDPC译码器FPGA全并行设计

往期博文 低密度奇偶校验码LDPC&#xff08;一&#xff09;——概述_什么是gallager构造-CSDN博客 低密度奇偶校验码LDPC&#xff08;二&#xff09;——LDPC编码方法-CSDN博客 低密度奇偶校验码LDPC&#xff08;三&#xff09;——QC-LDPC码概述-CSDN博客 低密度奇偶校验码…

HashSet在添加元素时,是如何判断元素重复的?

前言&#xff1a;我们知道Set中所存储的元素是不重复的&#xff0c;那么Set接口的实现类HashSet在添加元素时是怎么避免重复的呢&#xff1f; HashSet在添加元素时&#xff0c;是如何判断元素重复的? ● 在底层会先调用hashCode()&#xff0c;注意&#xff0c;Obje…

Hive安装教程-Hadoop集成Hive

文章目录 前言一、安装准备1. 安装条件2. 安装jdk3. 安装MySQL4. 安装Hadoop 二、安装Hive1. 下载并解压Hive2. 设置环境变量3. 修改配置文件3. 创建hive数据库4. 下载MySQL驱动5. 初始化hive数据库6. 进入Hive命令行界面7. 设置允许远程访问 总结 前言 本文将介绍安装和配置H…

Java高频面试之消息队列与分布式篇

有需要互关的小伙伴,关注一下,有关必回关,争取今年认证早日拿到博客专家 消息队列的基本作用&#xff1f; 异步通信&#xff1a;消息队列提供了异步通信的能力&#xff0c;发送方可以将消息发送到队列中&#xff0c;而无需等待接收方立即处理。发送方和接收方可以解耦&#x…

继深圳后,重庆与鸿蒙展开原生应用开发合作

截至2023年底&#xff0c;开源鸿蒙开源社区已有250多家生态伙伴加入&#xff0c;开源鸿蒙项目捐赠人达35家&#xff0c;通过开源鸿蒙兼容性测评的伙伴达173个&#xff0c;累计落地230余款商用设备&#xff0c;涵盖金融、教育、智能家居、交通、数字政府、工业、医疗等各领域。 …