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

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...