当前位置: 首页 > 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;可以用来实现这种功能。以下是一个完整的开发方…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...