力扣每日一题 超级饮料的最大强化能量 动态规划(dp)

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB,数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而,如果从一种能量饮料切换到另一种,你需要等待一小时来梳理身体的能量体系(在那个小时里你将不会获得任何强化能量)。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。  

示例 1: 输入:energyDrinkA = [1,3,1], energyDrinkB = [3,1,1] 输出:5

解释: 要想获得 5 点强化能量,需要选择只饮用能量饮料 A(或者只饮用 B)。

示例 2: 输入:energyDrinkA = [4,1,1], energyDrinkB = [1,1,3] 输出:7

解释:

• 第一个小时饮用能量饮料 A。

• 切换到能量饮料 B ,在第二个小时无法获得强化能量。

• 第三个小时饮用能量饮料 B ,并获得强化能量。   

 思路

这题题目描述有点不明确,概括一下题意就是有有两个饮料序列,分别代表饮料在1-n小时的能量值,开始时可以选择任意一种饮料饮用,每个小时只能选择一瓶饮料引用,如果你刚开始选的是第一种饮料,后面想要喝第二种饮料的话就需要等待一小时,即下一个小时无法饮用任何饮料,求第n小时过后能获得多少能量

题目中提到了如果要切换饮料种类就需要空等一小时,如果按照贪心的策略想的话这肯定是不合理的,所以这题不能用贪心解,所以当我们决定切换饮料,一定是我们可以获得更大收益的,这两天正好在学习dp,一瞬间就想到改用dp来解

设置数组 

long[][] dp=new long[n+1][2];

dp[i][0]代表第i时刻选择饮料A所能获得的最大能量

dp[i][1]代表第i时刻选择饮料B所能获得的最大能量

假设当前选择能量A又有两种两种可能

1.前一次选择的也是能量A  即 dp[i][0]= dp[i-1][0]  + energyDrinkA[i]

2.前一次选的是能量B         则 dp[i][0]= dp[i-2][1]   + energyDrinkA[i];

两者之中取较大值,可得

 dp[i][0]=Math.max(dp[i-1][0],dp[i-2][1])+energyDrinkA[i];

同理,饮料B的递推公式  dp[i][1]=Math.max(  dp[i-1][1] ,  dp[i-2][0] ) +  energyDrinkB[i];

初始化

        dp[0][0]=energyDrinkA[0];dp[0][1]=energyDrinkB[0];dp[1][0]=dp[0][0]+energyDrinkA[1];dp[1][1]=dp[0][1]+energyDrinkB[1];

下标为0的就是第一次喝饮料,直接取第一个饮料的能量即可

对于第二次选择,由于饮料的种类转移需要花费一个小时的时间,而前两次仅仅只有两个小时的时间,转移饮料种类无法获得任何能量,只会浪费第二个小时的时间,所以前两次都喝相同的饮料

 完整代码

class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {int n=energyDrinkA.length;long[][] dp=new long[n+1][2];dp[0][0]=energyDrinkA[0];dp[0][1]=energyDrinkB[0];dp[1][0]=dp[0][0]+energyDrinkA[1];dp[1][1]=dp[0][1]+energyDrinkB[1];for(int i=2;i<n;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-2][1])+energyDrinkA[i];dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0])+energyDrinkB[i];}return Math.max(dp[n-1][0],dp[n-1][1]);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/462442.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux高阶——1027—守护进程

1、守护进程的基本流程 1、父进程创建子进程&#xff0c;父进程退出 守护进程是孤儿进程&#xff0c;但是是工程师人为创建的孤儿进程&#xff0c;低开销模式运行&#xff0c;对系统没有压力 2、子进程&#xff08;守护进程&#xff09;脱离控制终端&#xff0c;创建新会话 …

抗疫物资管理:SpringBoot技术应用案例

目 录 摘 要 1 前 言 2 第1章 概述 2 1.1 研究背景 3 1.2 研究目的 3 1.3 研究内容 4 第二章 开发技术介绍 5 2.1相关技术 5 2.2 Java技术 6 2.3 MySQL数据库 6 2.4 Tomcat介绍 7 2.5 Spring Boot框架 8 第三章 系统分析 9 3.1 可行性分析 9 3.1.1 技术可行性 9 3.1.2 经济可行…

pandas——数据结构

一、series &#xff08;一&#xff09;创建series import pandas as pd#1.使用列表或数组创建Series # 使用列表创建Series&#xff0c;索引默认从0开始 s1 pd.Series([1, 2, 3]) print(s1) # 使用列表和自定义索引创建Series s2 pd.Series([1, 2, 3], index[a, b, c]) pr…

MySQL的SQL语句之触发器的创建和应用

触发器 Trigger 一.触发器 作用&#xff1a;当检测到某种数据表发生数据变化时&#xff0c;自动执行操作&#xff0c;保证数据的完整性&#xff0c;保证数据的一致性。 1.创建一个触发器 如上图所示&#xff0c;查看这个create的帮助信息的时候&#xff0c;这个create trig…

服务器数据恢复—DELL EqualLogic PS6100系列存储简介及如何收集故障信息?

DELL EqualLogic PS6100系列存储采用虚拟ISCSI SAN阵列&#xff0c;支持VMware、Solaris、Linux、Mac、HP-UX、AIX操作系统&#xff0c;提供全套企业级数据保护和管理功能&#xff0c;具有可扩展性和容错功能。DELL EqualLogic PS6100系列存储介绍&#xff1a; 1、上层应用基础…

什么是无限钱包系统?有什么优势?

在数字货币风起云涌的今天&#xff0c;一个名为“无限钱包系统”的创新平台正悄然引领着行业的变革。它不仅重新定义了数字资产的管理方式&#xff0c;更以卓越的安全性、便捷的操作体验以及前瞻性的技术理念&#xff0c;成为了广大数字货币爱好者心中的理想之选。 一、数字货币…

API网关 - JWT认证 ; 原理概述与具体实践样例

API网关主要提供的能力&#xff0c;就是协议转换&#xff0c;安全&#xff0c;限流等能力。 本文主要是分享 如何基于API网关实现 JWT 认证 。 包含了JWT认证的流程&#xff0c;原理&#xff0c;与具体的配置样例 API网关认证的重要性 在现代Web应用和微服务架构中&#x…

前端加密解密

一、 AES 加密与解密 高级加密标准(AES,Advanced Encryption Standard)为最常见的对称加密算法(微信小程序加密传输就是用这个加密算法的)。是一种对称加密算法也就是加密和解密用相同的密钥; 1.1 使用 crypto-js 实现 AES 加密 1.1.1 参数说明 data 要加密的明文key 秘钥iv …

基于知识引导提示的因果概念提取(论文复现)

基于知识引导提示的因果概念提取(论文复现) 本文所涉及所有资源均在传知代码平台可获取 文章目录 基于知识引导提示的因果概念提取(论文复现)论文概述论文方法提示构造器获取典型概念集聚类典型概念构建训练数据训练主题分类器概念提取器输入构造指针网络置信度评分训练损失…

【element ui系列】分享几种实现el-table表格单选的方法

在实际的开发中&#xff0c;经常会用到从表格中选择一条记录的情况&#xff0c;虽然官方给出的例子&#xff0c;但是给人感觉看起来不明显&#xff0c;于是&#xff0c;在此基础上做了改进。接下来&#xff0c;介绍两种常见的实现方法&#xff1a; 1、采用复选框(checkbox)实现…

63 mysql 的 行锁

前言 我们这里来说的就是 我们在 mysql 这边常见的 几种锁 行共享锁, 行排他锁, 表意向共享锁, 表意向排他锁, 表共享锁, 表排他锁 意向共享锁, 意向排他锁, 主要是 为了表粒度的锁获取的同步判断, 提升效率 意向共享锁, 意向排他锁 这边主要的逻辑意义是数据表中是否有任…

江协科技STM32学习- P26 UART串口外设

&#x1f680;write in front&#x1f680; &#x1f50e;大家好&#xff0c;我是黄桃罐头&#xff0c;希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流 &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd;​…

使用 ADB 在某个特定时间点点击 Android 设备上的某个按钮

前提条件 安装 ADB&#xff1a;确保你已经在计算机上安装了 Android SDK&#xff08;或单独的 ADB&#xff09;。并将其添加到系统环境变量中&#xff0c;以便你可以在命令行中运行 adb。 USB调试&#xff1a;确保 Android 设备已启用 USB 调试模式。这可以在设备的“设置” -…

mint-ui Picker 显示异常

mint-ui Picker 显示异常 现象 最近一个老项目页面显示异常&#xff0c;使用mint-ui Picker显示异常,直接显示成了 数据对象&#xff0c;而不是具体travelName 字段 组件 mint-ui Picker 使用方式(vue方式) // template <mt-picker :slots"slots" value-key…

FastAPI性能对比:同步vs异步

大家好&#xff0c;FastAPI已成为构建Python API的最流行框架之一&#xff0c;因其速度和易用性而广受欢迎。但在构建高性能应用程序时&#xff0c;使用同步&#xff08;sync&#xff09;还是异步&#xff08;async&#xff09;代码执行是很重要的问题。本文将通过现实世界的性…

wx.setNavigationBarColor动态设置导航栏颜色无效(亲测有效)

wx.setNavigationBarColor动态设置导航栏颜色无效&#xff08;亲测有效&#xff09; 问题描述问题分析问题解决注意 问题描述 wx.setNavigationBarColor({frontColor: #E6E6E6,backgroundColor: #E6E6E6 })上面的代码设置后导航栏颜色没有变化&#xff0c;查看了app.json 以及…

Blender进阶:贴图与UV

9 UV 9.1 贴图与UV UV&#xff0c;指定每个面顶点在贴图上的坐标 演示&#xff1a; 1、添加物体 2、添加贴图&#xff0c;即图片纹理节点 3、进入UV Edit工作区 4、右边&#xff0c;选择一个面 5、左边&#xff0c;选择一个面&#xff0c;移动这个面 9.2 电子表格 电子…

利用LangChain与LLM打造个性化私有文档搜索系统

我们知道LLM&#xff08;大语言模型&#xff09;的底模是基于已经过期的公开数据训练出来的&#xff0c;对于新的知识或者私有化的数据LLM一般无法作答&#xff0c;此时LLM会出现“幻觉”。针对“幻觉”问题&#xff0c;一般的解决方案是采用RAG做检索增强。 但是我们不可能把…

PostgreSQL-06-入门篇-集合运算

文章目录 1. UNION 组合多个查询的结果集简介带有 ORDER BY 子句的 UNION设置样例表PostgreSQL UNION 示例1) 简单的 PostgreSQL UNION 示例2) PostgreSQL UNION ALL 示例3) 带 ORDER BY 子句 UNION ALL 示例 2. INTERSECT 取交集简介带 ORDER BY 子句的 INTERSECT 操作Postgre…

云计算作业二Spark:问题解决备忘

安装spark 教程源地址&#xff1a;https://blog.csdn.net/weixin_52564218/article/details/141090528 镜像下载 教程给的官网下载地址很慢&#xff0c;https://archive.apache.org/dist/spark/spark-3.1.1/ 这里的镜像快很多&#xff1a; 清华软件源&#xff1a;https://mi…