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

3180. 执行操作可获得的最大总奖励 I

力扣刷题记录

dp 回溯

3180. 执行操作可获得的最大总奖励 I

思路

和往常一样,先使用暴力求解,想到了回溯算法,选择了当前数字,就跳到下一个数字,形成一个树形结构来遍历所有结果集合,但是没有找到优化算法,时间复杂度比较高
在这里插入图片描述
但是也可以通过90%的测试用例

没办法,只能思考动态规划的问题,没有想出来,查看题解
首先对数组进行排序
定义动态数组 dp[2 * max] , max表示最大的奖励数字
dp数组记录值为0或1,表示该下标的值是否能够被取到

最大的奖励数不可能超过2 * max,因此遍历奖励数组,当前值为x时,倒序k遍历 2 * x - 1到x,判断dp[k - x]是否可以取到,如果可以取到,那么dp[k]也可以达到,标记为1

最后遍历dp数组找到最大值即可

代码

var res int = 0func backTracking(rewardValues []int, curReward int, pos int){if curReward > res{res = curReward}if pos >= len(rewardValues){return}for i := pos; i < len(rewardValues); i++{if curReward < rewardValues[i]{curReward += rewardValues[i]backTracking(rewardValues, curReward, i + 1)curReward -= rewardValues[i]}}
}func maxTotalReward(rewardValues []int) int {sort.Ints(rewardValues)// res = 0// backTracking(rewardValues, 0, 0)max := rewardValues[len(rewardValues) - 1]dp := make([]int, 2 * max)dp[0] = 1for _, x := range rewardValues{for k := 2 * x - 1 ; k >= x ; k --{// k 表示能到达的最大总奖励if dp[k-x] == 1{dp[k] = 1}}}for i, val := range dp{if val == 1{res = i}}return res
}

不考虑排序算法的情况下
时间复杂度:O(n*max)
空间复杂度:O(max)

相关文章:

3180. 执行操作可获得的最大总奖励 I

力扣刷题记录 dp 回溯 3180. 执行操作可获得的最大总奖励 I 思路 和往常一样&#xff0c;先使用暴力求解&#xff0c;想到了回溯算法&#xff0c;选择了当前数字&#xff0c;就跳到下一个数字&#xff0c;形成一个树形结构来遍历所有结果集合&#xff0c;但是没有找到优化算…...

react18中的jsx 底层渲染机制相关原理

jsx 底层渲染机制 渲染 jsx 时&#xff0c;会先解析 jsx&#xff0c;生成一个虚拟 dom(virtual dom)。然后将虚拟 dom 渲染成真实 dom。如果 jsx 中包含事件&#xff0c;会将事件绑定到真实 dom 上。 虚拟 dom 对象&#xff0c;是框架内部构建的一套对象体系&#xff0c;对象…...

Spring Boot 实现文件上传下载功能

文章目录 一、原理分析1.1 请求类型1.2 服务器解析 二、功能实现2.1 创建项目并导入依赖2.2 文件上传功能实现2.2.1 文件上传 Service2.2.2 文件上传 Controller 2.3 文件下载功能实现2.3.1 文件下载 Service2.3.2 文件下载 Controller 2.4 文件上传前端代码(可选)2.4.1 上传文…...

ArcGIS 10.8 安装教程(含安装包)

目录 一、ArcGIS10.8二、安装链接三、安装教程四、ArcGIS实战 &#xff08;一&#xff09;ArcGIS10.8 1. 概述 ArcGIS 10.8是由美国Esri公司开发的GIS平台&#xff0c;用于处理、分析、显示和管理地理数据&#xff0c;并实现数据共享。它具有新特性和功能&#xff0c;性能更…...

【小白学机器学习16】 概率论的世界观2: 从正态分布去认识世界

目录 1 从正态分布说起 1.1 正态分布的定义 1.2 正态分布的名字 1.3 正态分布的广泛&#xff0c;和基础性 2 正态分布的公式和图形 2.1 正态分布 2.2 标准正态分布 3 正态分布的认识的3个层次 3.1 第1层次&#xff1a;个体的某个属性的样本值&#xff0c;服从正态分布…...

Python 爬虫项目实战:爬取某云热歌榜歌曲

一、网络爬虫的定义 网络爬虫&#xff08;Web Crawler&#xff09;&#xff0c;也成为网页蜘蛛或者网页机器人&#xff0c;是一种按照既定规则自动浏览网络并提取信息的程序。爬虫的主要用途包括数据采集、网络索以及内容抓取等。 二、爬虫基本原理 1、种子URL&#xff1a;爬…...

HCIP-HarmonyOS Application Developer 习题(十八)

&#xff08;判断&#xff09;1、在HarmonyOS有序公共事件中&#xff0c;高优先级订阅者可修改公共事件内容或处理结果&#xff0c;但不能终止公共事件处理。 答案&#xff1a;错误 分析&#xff1a;有序公共事件&#xff1a;主要场景是多个订阅者有依赖关系或者对处理顺序有要…...

操作系统学习笔记2.3互斥

文章目录 进程同步实现方式 进程互斥实现方式 软件实现方法硬件实现方法同步问题生产者-消费者问题问题描述解决方案代码解析 多生产者-多消费者问题问题描述 解决方案代码解析总结 抽烟者问题问题背景 同步与互斥的挑战解决方案实现步骤代码解释 关键点 进程同步 进程同步是指…...

LLM - 使用 Neo4j 可视化 GraphRAG 构建的 知识图谱(KG) 教程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/142938982 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 Neo4j …...

Linux 环境的搭建方式->远程登录->免密登录

个人主页&#xff1a;Jason_from_China-CSDN博客 所属栏目&#xff1a;Linux系统性学习_Jason_from_China的博客-CSDN博客 所属栏目&#xff1a;Linux知识点的补充_Jason_from_China的博客-CSDN博客 Linux 环境的搭建方式 Linux 环境的搭建主要有三种方式&#xff1a; 直接安…...

react18中的计算属性及useMemo的性能优化技巧

react18里面的计算属性和使用useMemo来提升组件性能的方法 计算属性 实现效果 代码实现 函数式组件极简洁的实现&#xff0c;就这样 import { useState } from "react"; function FullName() {const [firstName, setFirstName] useState("");const [la…...

Python 实现高效的 SM4 大文件加密解密实战指南20241024

Python 实现高效的 SM4 大文件加密解密实战指南 引言 在数据安全领域&#xff0c;使用对称加密算法如SM4进行数据保护非常常见。特别是当处理大文件时&#xff0c;合理的内存和块大小管理以及加密解密效率变得尤为重要。本文将分享如何使用Python进行大文件的SM4加密解密操作&…...

数据结构~红黑树

文章目录 一、红黑树的概念二、红黑树的定义三、红黑树的插入四、红黑树的平衡五、红黑树的验证六、红黑树的删除七、完整代码八、总结 一、红黑树的概念 红黑树是一棵二叉搜索树&#xff0c;他的每个结点增加⼀个存储位来表示结点的颜色&#xff0c;可以是红色或者黑色。通过…...

【ROS GitHub使用】

提示&#xff1a;环境配置为Ubuntu20.04&ROS Noetic 文章目录 前言一、创建工作空间目录二、尝试从GitHub上下载一个源码包&#xff0c;对它进行编译&#xff0c;运行这个源码包1.打开script文件夹&#xff0c;右键文件夹空白区域&#xff0c;选择在中端中打开&#xff1b;…...

批量处理文件权限:解决‘/usr/bin/chmod: Argument list too long’的有效方法

批量处理文件权限&#xff1a;解决‘/usr/bin/chmod: Argument list too long’的有效方法 错误原因解决方案1. 分批处理2. 使用xargs3. 增加ARG_MAX限制4. 使用脚本 结论 在Linux系统中&#xff0c;有时你可能会遇到这样的错误消息&#xff1a;“/usr/bin/chmod: Argument lis…...

数据结构——树——二叉树——大小堆

目录 1>>导言 2>>树 2.1>>树的相关术语 2.2>>树的表示和应用场景 3>>二叉树 3.1>>完全二叉树 3.2>>大小根堆 4>>结语 1>>导言 上篇小编将队列的内容给大家讲完了&#xff0c;这篇要步入新的篇章&#xff0c;请宝…...

Android Junit 单元测试 | 依赖配置和编译报错解决

问题 为什么在依赖中添加了testImplement在build APK的时候还是会报错&#xff1f;是因为没有识别到test文件夹是test源代码路径吗&#xff1f; 最常见的配置有: implementation - 所有源代码集(包括test源代码集)中都有该依赖库.testImplementation - 依赖关系仅在test源代码…...

ffmpeg视频滤镜: 裁剪-crop

滤镜简述 crop官网链接 > FFmpeg Filters Documentation crop滤镜可以对视频进行裁剪&#xff0c;并且这个滤镜可以接受一些变量比如时间和帧数&#xff0c;这样我们实现动态裁剪&#xff0c;从而实现一些特效。 滤镜使用 参数 out_w <string> ..…...

身份证归属地查询接口-在线身份证归属地查询-身份证归属地查询API

接口简介&#xff1a;输入身份证号码可查询到所属地区、出生年日月以及性别。 接口地址&#xff1a;https://www.wapi.cn/api_detail/60/167.html 在线核验&#xff1a;https://www.wapi.cn/icard.html 网站地址&#xff1a;https://www.wapi.cn 返回格式&#xff1a;json,xml,…...

ESP32 S3 怎么开发基于ESP-RTC的音视频实时交互的应用,用语AI陪伴的领域

在ESP32-S3平台上开发基于ESP-RTC的音视频实时交互应用&#xff0c;尤其是在AI陪伴领域&#xff0c;涉及到音视频数据的采集、编码、传输和解码。ESP32-S3 具备较强的处理能力&#xff0c;且拥有丰富的接口和模块支持&#xff0c;可以用来实现这种功能。以下是一个完整的开发方…...

AI驱动的网络安全:深度学习与LLM在威胁检测与教育中的应用

1. 项目概述&#xff1a;AI赋能的网络安全新范式在网络安全领域&#xff0c;我们正面临着一个日益严峻的悖论&#xff1a;一方面&#xff0c;攻击手段正变得前所未有的复杂和自动化&#xff1b;另一方面&#xff0c;74%的安全事件仍然源于人为因素。这种技术与人的双重挑战催生…...

NCCL watchdog timeout 先别只会加 timeout:PyTorch 新出的 Flight Recorder,真正值钱的是能把第一处 collective 分歧揪出来

NCCL watchdog timeout 先别只会加 timeout:PyTorch 新出的 Flight Recorder,真正值钱的是能把第一处 collective 分歧揪出来 很多人第一次遇到 NCCL watchdog timeout,第一反应都是三件事:查网络、调大 timeout、怀疑 NCCL 又炸了。这个顺序经常不够用。因为在很多真实训…...

从SMP到NUMA:聊聊多核CPU时代Linux内存管理是怎么‘进化’的

从SMP到NUMA&#xff1a;多核CPU时代的内存管理演进之路 2000年代初&#xff0c;当单核CPU的主频竞赛逐渐触及物理极限时&#xff0c;计算机架构师们面临一个关键抉择&#xff1a;如何在芯片上堆叠更多晶体管&#xff1f;答案最终指向了多核设计。但随之而来的内存访问瓶颈&…...

5分钟免费解锁iPhone激活锁:applera1n实用指南

5分钟免费解锁iPhone激活锁&#xff1a;applera1n实用指南 【免费下载链接】applera1n icloud bypass for ios 15-16 项目地址: https://gitcode.com/gh_mirrors/ap/applera1n 面对二手iPhone的激活锁界面&#xff0c;你是否感到束手无策&#xff1f;applera1n是一款专为…...

计算机毕业设计:Python医疗文本挖掘与可视化决策平台 Flask框架 随机森林 机器学习 疾病数据 智慧医疗 深度学习(建议收藏)✅

博主介绍&#xff1a;✌全网粉丝10W,前互联网大厂软件研发、集结硕博英豪成立工作室。专注于计算机相关专业项目实战6年之久&#xff0c;选择我们就是选择放心、选择安心毕业✌ > &#x1f345;想要获取完整文章或者源码&#xff0c;或者代做&#xff0c;拉到文章底部即可与…...

绝地求生罗技鼠标宏实战指南:5步实现高效压枪技巧

绝地求生罗技鼠标宏实战指南&#xff1a;5步实现高效压枪技巧 【免费下载链接】logitech-pubg PUBG no recoil script for Logitech gaming mouse / 绝地求生 罗技 鼠标宏 项目地址: https://gitcode.com/gh_mirrors/lo/logitech-pubg 对于《绝地求生》玩家来说&#xf…...

告别手动打断点:用GDB脚本自动化调试除零错误(附完整.gdb文件)

告别手动打断点&#xff1a;用GDB脚本自动化捕获除零错误实战指南 调试C/C程序时&#xff0c;最令人头疼的莫过于那些偶发的运行时错误。特别是当程序在压力测试或特定输入下突然崩溃&#xff0c;而开发者却无法稳定复现问题时&#xff0c;传统的调试方式往往显得力不从心。本…...

从DRM驱动看mmap:图解内存分配与映射的‘时机’与‘方式’如何影响性能

从DRM驱动看mmap&#xff1a;图解内存分配与映射的‘时机’与‘方式’如何影响性能 在图形驱动开发领域&#xff0c;内存管理始终是性能优化的关键战场。当你在调试一块高端显卡的DRM&#xff08;Direct Rendering Manager&#xff09;驱动时&#xff0c;是否曾遇到过这样的困惑…...

别再只会用传统插值了!深入浅出图解DuDoNet双域网络,如何同时修复Sinogram和CT图像

双域网络革命&#xff1a;从DuDoNet到DuDoNet的医学影像伪影消除实战 医学影像领域长期被金属伪影问题困扰——当患者体内存在金属植入物时&#xff0c;CT扫描图像会出现辐射状条纹和带状阴影&#xff0c;严重影响诊断准确性。传统解决方案如同用创可贴处理内伤&#xff1a;图像…...

SkillForge:构建可复用技能模块的标准化框架与实践指南

1. 项目概述与核心价值 最近在开源社区里&#xff0c;一个名为 SkillForge 的项目引起了我的注意。它的仓库地址是 kographh/skillforge &#xff0c;这个名字本身就很有意思——“技能锻造”。作为一名长期在技术一线摸爬滚打的开发者&#xff0c;我见过太多号称能“提升效…...