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

告别IDEA编译警告:深入解析JDK版本过时问题与多维度解决方案

1. 当IDEA开始"抱怨"&#xff1a;那些烦人的编译警告从哪来&#xff1f; 每次打开老项目&#xff0c;总能看到那个熟悉的黄色警告&#xff1a;"Warning:java: 源值1.5已过时&#xff0c;将在未来所有发行版中删除"。这个提示就像个唠叨的老朋友&#xff0c…...

i.MX 6UL/6ULL开发环境配置与驱动开发实战

1. i.MX 6UL/6ULL开发环境配置实战1.1 虚拟机环境搭建要点对于Windows平台下的i.MX开发&#xff0c;VirtualBox虚拟机是最经济实惠的选择。根据实际项目经验&#xff0c;建议配置如下&#xff1a;内存至少4GB&#xff08;复杂项目推荐8GB&#xff09;硬盘空间预留100GB&#xf…...

搜搜果:一种面向AI生成内容验真与品牌可见度监测的实现方案

1. 问题定义 随着大语言模型&#xff08;LLM&#xff09;广泛集成到搜索、问答、推荐等场景中&#xff0c;出现两个可观测的问题&#xff1a; 内容可信性问题&#xff1a;模型会以高置信度输出事实上不存在的实体、事件或引用&#xff08;幻觉&#xff0c;hallucination&#…...

AC鸭的迷宫按钮

题目描述AC鸭来到一个迷宫里&#xff0c;迷宫有 n 行 m 列。迷宫中有五种字符&#xff1a;A 表示 AC鸭一开始的位置。B 表示出口的位置。. 表示可以经过的空地。# 表示一开始不能经过的墙。K 表示按钮。AC鸭每一步可以向上、下、左、右四个方向移动一格&#xff0c;不能走出迷宫…...

FPGA上做图像压缩,别从零造轮子!聊聊DCT那些开源IP核与设计技巧

FPGA图像压缩实战&#xff1a;DCT开源IP核选型与架构优化指南 在嵌入式视觉系统开发中&#xff0c;JPEG图像压缩是FPGA工程师经常遇到的需求场景。当项目周期紧张且资源有限时&#xff0c;明智的开发者会优先考虑利用经过验证的开源IP核&#xff0c;而非从零开始实现离散余弦变…...

暗黑破坏神2存档编辑器:3步掌握d2s-editor的终极修改指南

暗黑破坏神2存档编辑器&#xff1a;3步掌握d2s-editor的终极修改指南 【免费下载链接】d2s-editor 项目地址: https://gitcode.com/gh_mirrors/d2/d2s-editor 还在为暗黑破坏神2中无尽刷装备而烦恼吗&#xff1f;想快速体验不同职业的build却不想花费数百小时&#xff…...

C++项目集成Tesseract 5.x踩坑实录:从编译选项到内存管理的完整避坑指南

C项目集成Tesseract 5.x踩坑实录&#xff1a;从编译选项到内存管理的完整避坑指南 在计算机视觉和文档处理领域&#xff0c;Tesseract OCR引擎以其开源免费、多语言支持和较高的识别准确率&#xff0c;成为众多C项目的首选集成方案。然而&#xff0c;从源码编译到生产环境部署&…...

Python地理空间数据处理技能库geoskills:简化GIS分析,提升开发效率

1. 项目概述&#xff1a;一个面向地理空间数据处理的技能库最近在GitHub上闲逛&#xff0c;发现了一个挺有意思的项目&#xff0c;叫geoskills&#xff0c;来自一个叫Cognitic-Labs的组织。光看名字&#xff0c;geo和skills的组合&#xff0c;就让我这个常年和数据打交道的人眼…...

别再乱接电阻了!手把手教你为DDR4/DDR5内存信号选对端接方案(附仿真对比)

别再乱接电阻了&#xff01;手把手教你为DDR4/DDR5内存信号选对端接方案&#xff08;附仿真对比&#xff09; 第一次调试DDR5内存接口时&#xff0c;我盯着示波器上扭曲的信号波形整整三天没合眼。当我把串联端接电阻从22Ω换成39Ω的瞬间&#xff0c;眼图突然像被施了魔法一样…...

aiomultiprocess 完全指南:突破 Python GIL 限制的终极并发解决方案

aiomultiprocess 完全指南&#xff1a;突破 Python GIL 限制的终极并发解决方案 【免费下载链接】aiomultiprocess Take a modern Python codebase to the next level of performance. 项目地址: https://gitcode.com/gh_mirrors/ai/aiomultiprocess 在 Python 编程世界…...