【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…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...