当前位置: 首页 > news >正文

Leetcode3259. 超级饮料的最大强化能量

Every day a Leetcode

题目来源:3259. 超级饮料的最大强化能量

解法1:记忆化搜索

本题的状态定义 dfs(i,j)。其中 j=0,1,分别表示最后选的是 energyDrinkA[i] 还是 energyDrinkB[i]。

为方便实现,把 energyDrinkA 和 energyDrinkB 加到一个长为 2 的二维数组 c 中。

分类讨论:

  • 继续选 c[j] 中的元素,那么下一个数选 c[j][i−1],需要解决的问题为:从下标 [0,i−1] 中选数字,且最后选的是 c[j] 中的元素的情况下,所选元素之和的最大值,即 dfs(i−1,j)。

  • 改成选 c[j⊕1] 中的元素,那么下一个数选 c[j⊕1][i−2],需要解决的问题为:从下标 [0,i−2] 中选数字,且最后选的是 c[j⊕1] 中的元素的情况下,所选元素之和的最大值,即 dfs(i−2,j⊕1)。其中 ⊕ 为异或运算,通过异或 1,可以把 0 变成 1,把 1 变成 0。

代码:

#
# @lc app=leetcode.cn id=3259 lang=python3
#
# [3259] 超级饮料的最大强化能量
## @lc code=start
class Solution:def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:n = len(energyDrinkA)energyDrink = (energyDrinkA, energyDrinkB)@cache  # 缓存装饰器,避免重复计算 dfs 的结果(记忆化)def dfs(i: int, j: int) -> int:if i < 0:return 0res1 = dfs(i - 1, j) + energyDrink[j][i]res2 = dfs(i - 2, j ^ 1) + energyDrink[j][i]return max(res1, res2)return max(dfs(n - 1, 0), dfs(n - 1, 1))
# @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(n),其中 n 为数组 energyDrinkA/energyDrinkB 的长度。由于每个状态只会计算一次,动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(n),单个状态的计算时间为 O(1),所以总的时间复杂度为 O(n)。

空间复杂度:O(n),其中 n 为数组 energyDrinkA/energyDrinkB 的长度。保存多少状态,就需要多少空间。

解法2:动态规划

代码:

/** @lc app=leetcode.cn id=3259 lang=cpp** [3259] 超级饮料的最大强化能量*/// @lc code=start
class Solution
{
public:long long maxEnergyBoost(vector<int> &energyDrinkA, vector<int> &energyDrinkB){int n = energyDrinkA.size();vector<array<long long, 2>> dp(n + 2);// 状态转移for (int i = 0; i < n; i++){dp[i + 2][0] = max(dp[i + 1][0], dp[i][1]) + energyDrinkA[i];dp[i + 2][1] = max(dp[i + 1][1], dp[i][0]) + energyDrinkB[i];}return max(dp[n + 1][0], dp[n + 1][1]);}
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(n),其中 n 为数组 energyDrinkA/energyDrinkB 的长度。

空间复杂度:O(n),其中 n 为数组 energyDrinkA/energyDrinkB 的长度。

相关文章:

Leetcode3259. 超级饮料的最大强化能量

Every day a Leetcode 题目来源&#xff1a;3259. 超级饮料的最大强化能量 解法1&#xff1a;记忆化搜索 本题的状态定义 dfs(i,j)。其中 j0,1&#xff0c;分别表示最后选的是 energyDrinkA[i] 还是 energyDrinkB[i]。 为方便实现&#xff0c;把 energyDrinkA 和 energyDri…...

Java题集(由入门到精通)03

此系列文章收录大量Java经典代码题&#xff08;也可以算是leetcode刷题指南&#xff09;&#xff0c;希望可以与大家一起努力学好Java。3、2、1&#xff0c;请看&#xff01; 目录 1.创建学生成绩表 2.冒泡排序 3.模拟彩票中奖 4.杨辉三角 1.创建学生成绩表 输入n个学生的…...

zblog自动生成文章插件(百度AI写作配图,图文并茂)

最近工作比较忙&#xff0c;导致自己的几个网站都无法手动更新&#xff0c;于是乎也想偷个懒把&#xff0c;让AI帮忙打理下自己的网站。我接触chatgpt等AI工具还是比较早了&#xff0c;从openai推出gpt3.5就一直在用&#xff0c;说实话&#xff0c;开始的时候用AI自动更新网站还…...

华为 HCIP-Datacom H12-821 题库 (4)

有需要题库的可以看主页置顶 V群仅进行学习交流 1.缺省情况下&#xff0c;广播型网络中运行 IS-IS 的路由器&#xff0c;DIS 发送 CSNP报文的周期为多少秒&#xff1f; A、10 B、3.3 C、30 D、40 答案&#xff1a;A 解析&#xff1a; 广播型网络中运行 IS-IS 的路由器&am…...

使用seq_file

在《使用procfs》一文的源码示例中有说到proc文件系统每次读取的数据只能是1个页,如果超过则需多次读取,这样的话会增加读取次数,增多系统调用次数,影响了整体的效率,故而才有seq file序列文件的出现,该项功能使得内核对于大文件的读取更加容易。 对于seq file,其结构…...

期货赫兹量化-种群优化算法:进化策略,(μ,λ)-ES 和 (μ+λ)-ES

进化策略&#xff08;Evolution Strategies, ES&#xff09;是一种启发式算法&#xff0c;旨在模仿自然选择的过程来解决复杂的优化问题&#xff0c;尤其在没有显式解、或搜索空间巨大的情况下表现良好。基于自然界的进化原理&#xff0c;进化策略通过突变、选择等遗传算子迭代…...

pytest实战演练

pytest实战演练 pycharm常见操作 创建项目使用虚拟环境 创建文件夹的时候建议使用的创建方式 这样创建是因为python3.0版本之后导包无区别&#xff0c;之前版本导包会报错的 _init_.py文件中建议为空不写内容 _all_[]的含义 是将列表中的方法或变量或类暴漏出去便于使用的生效…...

7、关于LoFTR

7、关于LoFTR LoFTR论文链接&#xff1a;LoFTR LoFTR的提出&#xff0c;是将Transformer模型的注意力机制在特征匹配方向的应用&#xff0c;Transformer的提取特征的机制&#xff0c;在自身进行&#xff0c;本文提出可以的两张图像之间进行特征计算&#xff0c;非常适合进行特…...

硬件工程师笔试面试知识器件篇——电感

目录​​​​​​​ 3、电感 3.1、基础 电感原理图 电感实物图 3.1.1、定义与单位 1)定义: 2) 单位: 3.1.2、物理原理 1)法拉第电磁感应定律: 2)楞次定律: 3.1.3、电感器的构造 3.1.4、类型 3.1.5、应用 3.1.6、特性 3.1.7、设计考虑 3.2、相关问题 3.…...

代码随想录八股训练营第三十六天| C++

前言 一、push_back()和emplace_back()的区别&#xff1f; 1.1.push_back(): 1.2.emplace_back(): 1.3.区别总结&#xff1a; 1.4.使用场景: 二、map dequeu list 的实现原理&#xff1f; 2.1.std::map: 2.2. std::deque: 2.3. std::list: 2.4. 区别总结: 总结 前言…...

学习计算机网络

a类0~127&#xff0c;b类128~191&#xff0c;c类192~223 网络地址&#xff1a;看子网掩码&#xff0c;分网络位和主机位&#xff0c;后面是主机位&#xff0c;主机位全部为0&#xff0c;网络地址。 直接广播地址&#xff1a;看子网掩码&#xff0c;分网络位和主机位&#xff…...

Django发送邮件

【图书介绍】《Django 5企业级Web应用开发实战&#xff08;视频教学版&#xff09;》_django 5企业级web应用开发实战(视频教学版)-CSDN博客 Django 5框架Web应用开发_夏天又到了的博客-CSDN博客 本文学习怎么使用Django发送邮件。 尽管使用Python的smtplib模块发送电子邮件…...

T7:咖啡豆识别

T7&#xff1a;咖啡豆识别 **一、前期工作**1.设置GPU,导入库2.导入数据3.查看数据 **二、数据预处理**1.加载数据2.可视化数据3.配置数据集 **三、构建CNN网络模型**1、手动搭建2、直接调用官方模型 **四、编译模型****五、训练模型****六、模型评估****七、预测**八、暂时总结…...

【MATLAB】FIR滤波器的MATLAB实现

FIR滤波器的MATLAB实现 FIR滤波器的设计fir1函数fir2函数 与IIR滤波器相比&#xff0c;FIR滤波器既有其优势也有其局限性。FIR滤波器的主要优点包括&#xff1a; 精确的线性相位响应&#xff1b;永远保持稳定性&#xff1b;设计方法通常是线性的&#xff1b;在硬件实现中具有更…...

【RabbitMQ之一:windows环境下安装RabbitMQ】

目录 一、下载并安装Erlang1、下载Erlang2、安装Erlang3、配置环境变量4、验证erlang是否安装成功 二、下载并安装RabbitMQ1、下载RabbitMQ2、安装RabbitMQ3、配置环境变量4、验证RabbitMQ是否安装成功5、启动RabbitMQ服务&#xff08;安装后服务默认自启动&#xff09; 三、安…...

ISO26262和Aspice之间的关联

ASPICE 介绍&#xff1a; ASPICE&#xff08;Automotive Software Process Improvement and Capability dEtermination&#xff09;是汽车软件过程改进及能力评定的模型&#xff0c;它侧重于汽车软件的开发过程。ASPICE 定义了一系列的过程和活动&#xff0c;包括需求管理、软…...

对极约束及其性质 —— 公式详细推导

Title: 对极约束及其性质 —— 公式详细推导 文章目录 前言1. 对极约束 (Epipolar Constraint)2. 坐标转换 (Coordinate Transformations)3. 像素坐标 (Pixel Coordinates)4. 像素坐标转换 (Transformations of Pixel Coordinates)5. 本质矩阵 (Essential Matrix)6. 线坐标 (Co…...

【论文精读】SCINet-基于降采样和交互学习的时序卷积模型

《SCINet: Time Series Modeling and Forecasting with Sample Convolution and Interaction》的作者团队来自香港中文大学,发表在NeurIPS 2022会议上。 动机 该论文的出发点是观察到时间序列数据具有独特的属性:即使在将时间序列下采样成两个子序列后,时间关系(例如数据…...

深度学习与大模型第1课环境搭建

文章目录 深度学习与大模型第1课环境搭建1. 安装 Anaconda2. 修改环境变量2.1 修改 .condarc 文件2.2 使用 Anaconda Prompt 修改环境变量 3. 新建 .ipynb 文件 机器学习基础编程&#xff1a;常见问题&#xff1a; 深度学习与大模型第1课 环境搭建 1. 安装 Anaconda 首先&am…...

JDK新特性

LTS Record jdk16 不是方法 是一个定 # Sealed Class/Interface jdk17 限制只能由某些类继承 CompletableFuture jkd8 PatternMatching of instanceOf jdk16 switch expressions jdk14 Stream.collect() Collector Collector API Collector.groupBy Collector实战 1. …...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...