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 思路 和往常一样,先使用暴力求解,想到了回溯算法,选择了当前数字,就跳到下一个数字,形成一个树形结构来遍历所有结果集合,但是没有找到优化算…...
react18中的jsx 底层渲染机制相关原理
jsx 底层渲染机制 渲染 jsx 时,会先解析 jsx,生成一个虚拟 dom(virtual dom)。然后将虚拟 dom 渲染成真实 dom。如果 jsx 中包含事件,会将事件绑定到真实 dom 上。 虚拟 dom 对象,是框架内部构建的一套对象体系,对象…...
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实战 (一)ArcGIS10.8 1. 概述 ArcGIS 10.8是由美国Esri公司开发的GIS平台,用于处理、分析、显示和管理地理数据,并实现数据共享。它具有新特性和功能,性能更…...
【小白学机器学习16】 概率论的世界观2: 从正态分布去认识世界
目录 1 从正态分布说起 1.1 正态分布的定义 1.2 正态分布的名字 1.3 正态分布的广泛,和基础性 2 正态分布的公式和图形 2.1 正态分布 2.2 标准正态分布 3 正态分布的认识的3个层次 3.1 第1层次:个体的某个属性的样本值,服从正态分布…...
Python 爬虫项目实战:爬取某云热歌榜歌曲
一、网络爬虫的定义 网络爬虫(Web Crawler),也成为网页蜘蛛或者网页机器人,是一种按照既定规则自动浏览网络并提取信息的程序。爬虫的主要用途包括数据采集、网络索以及内容抓取等。 二、爬虫基本原理 1、种子URL:爬…...
HCIP-HarmonyOS Application Developer 习题(十八)
(判断)1、在HarmonyOS有序公共事件中,高优先级订阅者可修改公共事件内容或处理结果,但不能终止公共事件处理。 答案:错误 分析:有序公共事件:主要场景是多个订阅者有依赖关系或者对处理顺序有要…...
操作系统学习笔记2.3互斥
文章目录 进程同步实现方式 进程互斥实现方式 软件实现方法硬件实现方法同步问题生产者-消费者问题问题描述解决方案代码解析 多生产者-多消费者问题问题描述 解决方案代码解析总结 抽烟者问题问题背景 同步与互斥的挑战解决方案实现步骤代码解释 关键点 进程同步 进程同步是指…...
LLM - 使用 Neo4j 可视化 GraphRAG 构建的 知识图谱(KG) 教程
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/142938982 免责声明:本文来源于个人知识与公开资料,仅用于学术交流,欢迎讨论,不支持转载。 Neo4j …...
Linux 环境的搭建方式->远程登录->免密登录
个人主页:Jason_from_China-CSDN博客 所属栏目:Linux系统性学习_Jason_from_China的博客-CSDN博客 所属栏目:Linux知识点的补充_Jason_from_China的博客-CSDN博客 Linux 环境的搭建方式 Linux 环境的搭建主要有三种方式: 直接安…...
react18中的计算属性及useMemo的性能优化技巧
react18里面的计算属性和使用useMemo来提升组件性能的方法 计算属性 实现效果 代码实现 函数式组件极简洁的实现,就这样 import { useState } from "react"; function FullName() {const [firstName, setFirstName] useState("");const [la…...
Python 实现高效的 SM4 大文件加密解密实战指南20241024
Python 实现高效的 SM4 大文件加密解密实战指南 引言 在数据安全领域,使用对称加密算法如SM4进行数据保护非常常见。特别是当处理大文件时,合理的内存和块大小管理以及加密解密效率变得尤为重要。本文将分享如何使用Python进行大文件的SM4加密解密操作&…...
数据结构~红黑树
文章目录 一、红黑树的概念二、红黑树的定义三、红黑树的插入四、红黑树的平衡五、红黑树的验证六、红黑树的删除七、完整代码八、总结 一、红黑树的概念 红黑树是一棵二叉搜索树,他的每个结点增加⼀个存储位来表示结点的颜色,可以是红色或者黑色。通过…...
【ROS GitHub使用】
提示:环境配置为Ubuntu20.04&ROS Noetic 文章目录 前言一、创建工作空间目录二、尝试从GitHub上下载一个源码包,对它进行编译,运行这个源码包1.打开script文件夹,右键文件夹空白区域,选择在中端中打开;…...
批量处理文件权限:解决‘/usr/bin/chmod: Argument list too long’的有效方法
批量处理文件权限:解决‘/usr/bin/chmod: Argument list too long’的有效方法 错误原因解决方案1. 分批处理2. 使用xargs3. 增加ARG_MAX限制4. 使用脚本 结论 在Linux系统中,有时你可能会遇到这样的错误消息:“/usr/bin/chmod: Argument lis…...
数据结构——树——二叉树——大小堆
目录 1>>导言 2>>树 2.1>>树的相关术语 2.2>>树的表示和应用场景 3>>二叉树 3.1>>完全二叉树 3.2>>大小根堆 4>>结语 1>>导言 上篇小编将队列的内容给大家讲完了,这篇要步入新的篇章,请宝…...
Android Junit 单元测试 | 依赖配置和编译报错解决
问题 为什么在依赖中添加了testImplement在build APK的时候还是会报错?是因为没有识别到test文件夹是test源代码路径吗? 最常见的配置有: implementation - 所有源代码集(包括test源代码集)中都有该依赖库.testImplementation - 依赖关系仅在test源代码…...
ffmpeg视频滤镜: 裁剪-crop
滤镜简述 crop官网链接 > FFmpeg Filters Documentation crop滤镜可以对视频进行裁剪,并且这个滤镜可以接受一些变量比如时间和帧数,这样我们实现动态裁剪,从而实现一些特效。 滤镜使用 参数 out_w <string> ..…...
身份证归属地查询接口-在线身份证归属地查询-身份证归属地查询API
接口简介:输入身份证号码可查询到所属地区、出生年日月以及性别。 接口地址:https://www.wapi.cn/api_detail/60/167.html 在线核验:https://www.wapi.cn/icard.html 网站地址:https://www.wapi.cn 返回格式:json,xml,…...
ESP32 S3 怎么开发基于ESP-RTC的音视频实时交互的应用,用语AI陪伴的领域
在ESP32-S3平台上开发基于ESP-RTC的音视频实时交互应用,尤其是在AI陪伴领域,涉及到音视频数据的采集、编码、传输和解码。ESP32-S3 具备较强的处理能力,且拥有丰富的接口和模块支持,可以用来实现这种功能。以下是一个完整的开发方…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合
无论是python,或者java 的大型项目中,都会涉及到 自身平台微服务之间的相互调用,以及和第三发平台的 接口对接,那在python 中是怎么实现的呢? 在 Python Web 开发中,FastAPI 和 Django 是两个重要但定位不…...
医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
