当前位置: 首页 > 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. …...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...