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

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...