【Leetcode 每日一题 - 补卡】3259. 超级饮料的最大强化能量
问题背景
来自未来的体育科学家给你两个整数数组 e n e r g y D r i n k A energyDrinkA energyDrinkA 和 e n e r g y D r i n k B energyDrinkB energyDrinkB,数组长度都等于 n n n。这两个数组分别代表 A A A、 B B B 两种不同能量饮料每小时所能提供的强化能量。
你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而,如果从一种能量饮料切换到另一种,你需要等待一小时来梳理身体的能量体系(在那个小时里你将不会获得任何强化能量)。
返回在接下来的 n n n 小时内你能获得的 最大 总强化能量。
注意 你可以选择从饮用任意一种能量饮料开始。
数据约束
- n = = e n e r g y D r i n k A . l e n g t h = = e n e r g y D r i n k B . l e n g t h n == energyDrinkA.length == energyDrinkB.length n==energyDrinkA.length==energyDrinkB.length
- 3 ≤ n ≤ 1 0 5 3 \le n \le 10 ^ 5 3≤n≤105
- 1 ≤ e n e r g y D r i n k A [ i ] , e n e r g y D r i n k B [ i ] ≤ 1 0 5 1 \le energyDrinkA[i], energyDrinkB[i] \le 10 ^ 5 1≤energyDrinkA[i],energyDrinkB[i]≤105
解题过程
题目要求从两个数组中每次选一个数累计得到最大值,如果某轮将要选择与上一次选择中不同的数组中的数,那么这一轮不能直接选择从另一个数组中选择。
考虑递归,从前往后或者从后往前枚举都可以。每一轮选取当前值的前提,是选取同一数组的上一个数或者选取不同数组的上上个数。
为了表示方便,将两个数组拼成一个二维数组 e n e r g y D r i n k energyDrink energyDrink,根据另一维度的下标确定从哪个数组中取值。
因此,状态转移方程: d f s ( i , j ) = m a x ( d f s ( i − 1 , j ) , d f s ( i − 2 , j ⊕ 1 ) ) + c [ j ] [ i ] dfs(i,j) = max(dfs(i − 1,j), dfs(i − 2,j \oplus 1)) + c[j][i] dfs(i,j)=max(dfs(i−1,j),dfs(i−2,j⊕1))+c[j][i]。
递归入口 是 m a x ( d f s ( 0 , 0 ) , d f s ( 0 , 1 ) ) max(dfs(0, 0), dfs(0, 1)) max(dfs(0,0),dfs(0,1)),表示选取两个数组中较大的第一个数。
递归边界 是 i > e n e r g y D r i n k [ 0 ] . l e n g t h − 1 i > energyDrink[0].length - 1 i>energyDrink[0].length−1,表示已经选择完数组中的数。
递归的做法实现完成之后,可以把它等效地翻译成递推。
答案为 m a x ( d p [ n + 1 ] [ 0 ] , d p [ n + 1 ] [ 1 ] ) max(dp[n + 1][0], dp[n + 1][1]) max(dp[n+1][0],dp[n+1][1]),表示枚举最后一个数之后产生的最终结果。
初始值为 d p [ 0 ] [ j ] = d p [ 1 ] [ j ] = 0 dp[0][j]=dp[1][j]=0 dp[0][j]=dp[1][j]=0,表示尚未枚举任何数时,状态转移数组中初始为空。
具体实现
递归
class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {// 用原来的两个数组定义二维数组,注意一下这个写法int[][] energyDrink = {energyDrinkA, energyDrinkB};// 定义同等规模的 memo 数组用于记忆化搜索,防止炸内存long[][] memo = new long[energyDrinkA.length][2];// 递归入口, 也是答案return Math.max(dfs(0, 0, energyDrink, memo), dfs(0, 1, energyDrink, memo));}private long dfs(int i, int j, int[][] energyDrink, long[][] memo) {// 递归边界,数组下标越界范围 0if(i > energyDrink[0].length - 1) {return 0;}// 已经存储过的答案直接返回if(memo[i][j] > 0) {return memo[i][j];}// 求当前轮次的最大值并存储,注意新定义的二维数组形状,用 energyDrink[j][i] 来取值return memo[i][j] = Math.max(dfs(i + 1, j, energyDrink, memo), dfs(i + 2, j ^ 1, energyDrink, memo)) + energyDrink[j][i];}
}
递推
class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {int n = energyDrinkA.length;// 定义状态转移数组 dp,由于状态可能和上上个数有关,数组规模需要相应地扩大long[][] dp = new long[n + 2][2];for(int i = 0; i < n; i++) {dp[i + 2][0] = Math.max(dp[i + 1][0], dp[i][1]) + energyDrinkA[i];dp[i + 2][1] = Math.max(dp[i + 1][1], dp[i][0]) + energyDrinkB[i];}return Math.max(dp[n + 1][0], dp[n + 1][1]);}
}
梳理总结
二进制状态转换
如果一个状态变量 s t a t u s status status非零即一,那么有两种方法将它转换成另一种状态:
- s t a t u s = 1 − s t a t u s status = 1 - status status=1−status
- s t a t u s = s t a t u s ⊕ 1 status = status \oplus 1 status=status⊕1
相关文章:
【Leetcode 每日一题 - 补卡】3259. 超级饮料的最大强化能量
问题背景 来自未来的体育科学家给你两个整数数组 e n e r g y D r i n k A energyDrinkA energyDrinkA 和 e n e r g y D r i n k B energyDrinkB energyDrinkB,数组长度都等于 n n n。这两个数组分别代表 A A A、 B B B 两种不同能量饮料每小时所能提供的强化…...
【人工智能】使用Python实现序列到序列(Seq2Seq)模型进行机器翻译
解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 序列到序列(Sequence-to-Sequence, Seq2Seq)模型是解决序列输入到序列输出任务的核心架构,广泛应用于机器翻译、文本摘要和问答系统等自然语言处理任务中。本篇文章深入介绍 Seq2Seq 模型的原理及其核心组件(…...
量化交易系统开发-实时行情自动化交易-4.4.1.做市策略实现
19年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 接下来继续说说做市策略实现。 做市策…...

Pinia之2:计数器案例、computed函数、异步action、storeToRefs函数、pinia调试
欢迎来到“雪碧聊技术”CSDN博客! 在这里,您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者,还是具有一定经验的开发者,相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导,我将…...

Microsoft Excel如何插入多行
1.打开要编辑的excel表,在指定位置,鼠标右键点击“插入”一行 2.按住shift键,鼠标的光标箭头会变化成如下图所示 3.一直按住shift键和鼠标左键,往下拖动,直至到插入足够的行...

Redis【1】- 如何阅读Redis 源码
1 Redis 的简介 Redis 实际上是简称,全称为 Remote Dictionary Server (远程字典服务器),由 Salvatore Sanfilippo 写的高性能 key-value 存储系统,其完全开源免费,遵守 BSD 协议。Redis 与其他 key-value 缓存产品(如…...
shell查看服务器的内存和CPU,实时使用情况
要查看服务器的内存和 CPU 实时使用情况,可以使用以下方法和命令: 1. 使用 top 运行 top 命令以显示实时的系统性能信息,包括 CPU 和内存使用情况。 top按 q 退出。输出内容包括: CPU 使用率:位于顶部,标…...

软件/游戏提示:mfc42u.dll没有被指定在windows上运行如何解决?多种有效解决方法汇总分享
遇到“mfc42u.dll 没有被指定在 Windows 上运行”的错误提示,通常是因为系统缺少必要的运行库文件或文件损坏。以下是多种有效的解决方法,可以帮助你解决这个问题: 原因分析 出现这个错误的原因是Windows无法找到或加载MFC42u.dll文件。这可…...

《Python基础》之函数、模块与库
目录 简介 一、函数 1、数学类函数 2、聚合类函数 3、和进制相关的函数 4、字符类函数 5、类型转换相关函数 6、获取输出类函数 二、模块与库的使用方法 1、模块和库的导入方法 2、第三方模块的下载 下载方法 简介 在Python编程的世界中,函数、模块和库是…...

selinux和防火墙实验
1 、 selinux 的说明 SELinux 是 Security-Enhanced Linux 的缩写,意思是安全强化的 linux 。 SELinux 主要由美国国家安全局( NSA )开发,当初开发的目的是为了避免资源的误用。 系统资源都是通过程序进行访问的,如…...

k8s Init:ImagePullBackOff 的解决方法
kubectl describe po (pod名字) -n kube-system 可查看pod所在的节点信息 例如: kubectl describe po calico-node-2lcxx -n kube-system 执行拉取前先把用到的节点的源换了 sudo mkdir -p /etc/docker sudo tee /etc/docker/daemon.json <<-EOF {"re…...

Spring AOP相关知识详解
难 文章目录 1.AOP介绍1.1 面向切面编程 - Aspect Oriented Programming (AOP)1.2 优点 2.AOP的概念2.1 连接点、切入点、通知、切面:2.2 注解2.2.1 通知类型2.2.1.1 通知的优先级排序 2.2.2 其他重要注解2.2.3 示例代码(四种通知) 3.Spring …...
selinux和防火墙
第七章 selinux 一、selinux的说明 SELinux:安全强化的 linux,Security-Enhanced Linux的缩写 SELinux : 由美国国家安全局( NSA )开发,目的是为了避免资源的误用 SELinux: 是对程序、文件等权…...

【vue for beginner】Composition API 和 Options API 的区别
🌈Don’t worry , just coding! 内耗与overthinking只会削弱你的精力,虚度你的光阴,每天迈出一小步,回头时发现已经走了很远。 📗概念 vue2中的方式叫Options API ,vue3中叫Composition API。 Composition…...

jmeter5.6.3安装教程
一、官网下载 需要提前配置好jdk的环境变量 jmeter官网:https://jmeter.apache.org/download_jmeter.cgi 选择点击二进制的zip文件 下载成功后,默认解压下一步,更改安装路径就行(我安装在D盘) 实用jmeter的bin目录作为系统变量 然后把这…...
关于Spring基础了解
Spring简介 Spring框架是一个开源的Java应用框架,旨在简化企业级应用程序的开发。它提供了一系列强大的工具和服务,帮助开发者构建高质量的Java应用程序。Spring框架的核心理念是使开发过程更加模块化、可测试和可维护。 主要特性 依赖注入(…...

输入json 达到预览效果
下载 npm i vue-json-pretty2.4.0 <template><div class"newBranchesDialog"><t-base-dialogv-if"addDialogShow"title"Json数据配置"closeDialog"closeDialog":dialogVisible"addDialogShow":center"…...

DataLoade类与list ,iterator ,yield的用法
1 问题 探索DataLoader的属性,方法 Vscode中图标含意 list 与 iterator 的区别,尤其yield的用法 2 方法 知乎搜索DataLoader的属性,方法 pytorch基础的dataloader类是 from torch.utils.data.dataloader import Dataloader 其主要的参数如下&…...
model_selection.train_test_split函数介绍
目录 model_selection.train_test_split函数实战 model_selection.train_test_split函数 model_selection.train_test_split 是 Scikit-Learn 中用于将数据集拆分为训练集和测试集的函数。这个函数非常有用,因为在机器学习中,我们通常需要将数据集分为训…...
Springboot 读取 resource 目录下的Excel文件并下载
代码示例: GetMapping("/download") public void download(HttpServletResponse response) {try {String filename "测试.xls";OutputStream outputStream response.getOutputStream();// 获取springboot resource 路径下的文件InputStream inputStream…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...