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

LeetCode——动态规划(五)

刷题顺序及思路来源于代码随想录,网站地址:https://programmercarl.com 

目录

121. 买卖股票的最佳时机 - 力扣(LeetCode)

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

123. 买卖股票的最佳时机 III - 力扣(LeetCode)


121. 买卖股票的最佳时机 - 力扣(LeetCode)

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

/*** @author light* @Description 买股票的最佳时机。** (思路:分为持有和不持有状态:(持有不代表当天买入,持有是一种状态,同理不持有也是* 1.持有:以前就持有或者当天才持有* 2.不持有:以前就不持有或者当天卖出不持有* @create 2023-10-13 13:48*/
public class MaxProfitTest {public int maxProfit(int[] prices) {//dp[i][0]:第i天不持有股票,所获得的最大利润//dp[i][1]:第i天持有股票,所获得的最大利润int[][] dp=new int[prices.length][2];dp[0][0]=0;dp[0][1]=-prices[0];for (int i =1; i <prices.length; i++) {dp[i][0]= Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); //不持有:以前不持有/现在卖出dp[i][1]= Math.max(dp[i-1][1],-prices[i]);  //持有:以前持有/现在买入}return dp[prices.length-1][0];}
}

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。

/*** @author light* @Description 买股票的最佳时机II** (两种情况:分为持有和不持有* 1.持有:以前就持有/以前不持有现在持有* 2.不持有:以前就不持有/以前持有现在不持有* @create 2023-10-13 15:11*/
public class MaxProfit2Test {public int maxProfit(int[] prices) {//dp[i][0]:第i天持有股票,所获得的最大利润//dp[i][1]:第i天不持有股票,所获得的最大利润int[][] dp=new int[prices.length][2];dp[0][0]=-prices[0];dp[0][1]=0;for (int i = 0; i < prices.length; i++) {//持有:区别于买股票的最佳时机那道题,注意这里题干是每一天,意思是持有情况可能在前一天有利润情况下持有本次股票dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]= Math.max(dp[i-1][1],dp[i-1][0]+prices[i]); //不持有}return dp[prices.length-1][1];}
}

123. 买卖股票的最佳时机 III - 力扣(LeetCode)

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
/*** @author light* @Description 买股票的最佳时机III** (思路:最多能买两只股票则有共有5个状态* 0.没有操作* 1.第一次持有股票--第一次一直持有/之前不持有,现在持有* 2.第一次不持有股票--第一次一直不持有/之前持有,现在不持有* 3.第二次持有股票--第二次一直持有/第一次后不持有,现在持有* 4.第二次不持有股票--第一次后一直不持有/第一次后不持有,现在持有* @create 2023-10-13 16:11*/
public class MaxProfit3Test {public int maxProfit(int[] prices) {int[][] dp=new int[prices.length][5];dp[0][0]=0;dp[0][1]=-prices[0];dp[0][2]=0;dp[0][3]=-prices[0];dp[0][4]=0;for (int i = 1; i < prices.length; i++) {dp[i][1]= Math.max(dp[i][0]-prices[i],dp[i-1][1]);dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);}return dp[prices.length-1][4];}}

相关文章:

LeetCode——动态规划(五)

刷题顺序及思路来源于代码随想录&#xff0c;网站地址&#xff1a;https://programmercarl.com 目录 121. 买卖股票的最佳时机 - 力扣&#xff08;LeetCode&#xff09; 122. 买卖股票的最佳时机 II - 力扣&#xff08;LeetCode&#xff09; 123. 买卖股票的最佳时机 III …...

与HTTP相关的各种概念

网络世界 网络世界中最重要的一个名词就是互联网&#xff08;Internet&#xff09;,它以TCP/IP协议族为基础&#xff0c;构建成了一望无际的信息传输网络。而我们通常所说的“上网”&#xff0c;主要就是访问互联网的一个子集——万维网&#xff08;World Wide Web&#xff09…...

CentOS 7 编译安装Boost

1、前提条件 linux平台/CentOS 7 下要编译安装Boost除gcc和gcc-c之外&#xff0c;还需要两个开发库&#xff1a;bzip2-devel 和python-devel &#xff0c;因此在安装前应该先保证这两个库已经安装。 安装指令: yum install bzip2 bzip2-devel bzip2-libs python-devel Cent…...

vue图表制作

Vue.js是一个非常流行的JavaScript框架&#xff0c;可以用于开发交互式Web应用程序。Vue.js的优点之一是它的灵活性和可扩展性。因此&#xff0c;可以使用Vue.js与许多其他库和框架集成&#xff0c;包括图表库。 下面是使用Vue.js制作图表的一些步骤&#xff1a; 1.选择一个适…...

使用 GitHub Action 自动更新 Sealos 集群的应用镜像

在 IT 领域&#xff0c;自动化无疑已成为提高工作效率和减少人为错误的关键。Sealos 作为一个强大的云操作系统&#xff0c;已经为许多企业和开发者提供了稳定可靠的服务。与此同时&#xff0c;随着技术不断发展&#xff0c;集成更多的功能和服务变得尤为重要。考虑到这一点&am…...

windows频繁更新问题解决方案

解决方案&#xff1a;将更新策略增加到无穷大 1.windowsr 输入regedit 2.找到&#xff1a;HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings 3.右键新建DWORD32 4.命名&#xff1a;FlightSettingsMaxPauseDays 5.双击&#xff1a;数值数据改为4321 基数&#…...

day05-前后端项目上传到gitee、后端多方式登录接口、发送短信功能、发送短信封装、短信验证码接口、短信登录接口

1 前后端项目上传到gitee 2 后端多方式登录接口 2.1 序列化类 2.2 视图类 2.3 路由 3 发送短信功能 4 发送短信封装 4.0 目录结构 4.1 settings.py 4.2 sms.py 5 短信验证码接口 6 短信登录接口 6.1 视图类 6.2 序列化类 1 前后端项目上传到gitee # 我们看到好多开源项目…...

046:mapboxGL加载天地图路网图+标记(wmts方式)

第046个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中加载天地图路网图+标记(wmts方式)。瓦片中的url地址引用的是天地图的wmts的形式。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共99行)相关AP…...

【ICer的脚本练习】tcl语法熟悉和工具tcl的实例

系列的目录说明请见:ICer的脚本练习专栏介绍与全流程目录_尼德兰的喵的博客-CSDN博客 前言 TCL(Tool Command Language)是一种简单但功能强大的脚本语言,它经常用于自动化任务、测试和快速原型开发。你看这个名字就能知道,这个语言最主要的作用就是用来操作工具,尤其我们…...

uniapp+vue3+ts+uview-plus搭建项目步骤

创建项目 使用Vue3/Vite版&#xff0c;创建以 typescript 开发的工程 下载仓库 DCloud/uni-preset-vue - Gitee.com node版本&#xff1a;v16.18.0 npm版本&#xff1a; v8.19.2 依赖下载 解压之后&#xff0c;在vscode打开 通过终端运行 npm 命令下载依赖&#xff1a;npm ins…...

在PHP中,可以使用不同的加密算法(如MD5、SHA1、SHA256)结合RSA算法进行公钥加密和私钥解密。

下面是使用这三种算法进行加密和解密的示例代码&#xff1a; // 生成RSA密钥对 $keyPair openssl_pkey_new(array(private_key_bits > 2048,private_key_type > OPENSSL_KEYTYPE_RSA, ));// 获取私钥和公钥 openssl_pkey_export($keyPair, $privateKey); $publicKey o…...

第六章:路由交换机及操作系统

路由交换机及操作系统 一、路由器与交换机的作用与特点1.路由器1.1 作用1.2 特点 2.交换机2.1 作用2.2 特点 二、H3C路由器与交换机介绍1. 路由器2. 交换机 三、 H3C网络设备操作系统Comware1. 介绍2. 特点![在这里插入图片描述](https://img-blog.csdnimg.cn/2b24103028654878…...

Kafka SASL认证授权(六)全方位性能测试

Kafka SASL认证授权(六)全方位性能测试。 官网地址:https://kafka.apache.org/ 一、场景 线上已经有kafka集群,服务运行稳定。但是因为产品升级,需要对kakfa做安全测试,也就是权限验证。 但是增加权限验证,会不会对性能有影响呢?影响大吗?不知道呀! 因此,本文就此…...

基于nodejs+vue校园失物招领平台设计与实现

科学技术日新月异的如今&#xff0c;计算机在生活各个领域都占有重要的作用&#xff0c;尤其在信息管理方面&#xff0c;在这样的大背景下&#xff0c;学习计算机知识不仅仅是为了掌握一种技能&#xff0c;更重要的是能够让它真正地使用到实目 录 摘 要 I ABSTRACT II 目 录 II…...

Open Winding-PMSM-开绕组永磁同步电机基本介绍

文章目录 前言简介Open Widing电机数学模型零序模型 双逆变器调制零序电流抑制基本思路 前言 最近看了些Open Winding永磁同步电机及其控制策略的文献资料&#xff0c;现做个总结。未来的研究方向也大概率围绕Open Winding开展&#xff0c;期待同行交流学习。 简介 开绕组(O…...

uniapp 一次性上传多条视频 u-upload accept=“video“ uni.chooseMedia uni.uploadFile

方式 一 部分安卓机 只能一条一条传视频 文档地址 uview 2.0 Upload 上传组件 html <view class"formupload"><u-upload accept"video":fileList"fileList3" afterRead"afterRead" delete"deletePic" name"…...

CentOS7卸载硬盘报错:umount: /data: target is busy.

问题描述 umount: /data: target is busy. 问题分析 硬盘正在被使用&#xff0c;不能被卸载。 解决方案 查看哪些程序在使用硬盘 [rootlocalhost ~]# lsof /data/ COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME mysqld 15655 polkitd cwd …...

Chrome插件精选 — 鼠标手势插件

Chrome实现同一功能的插件往往有多款产品&#xff0c;逐一去安装试用耗时又费力&#xff0c;在此为某一类型插件记录下比较好用的一款或几款&#xff0c;便于节省尝试的时间和精力。 下面是两款比较好用的鼠标手势插件&#xff0c;支持很多设置选项&#xff0c;可以自定义手势&…...

JMeter分布式

一 分布式注意事项 关闭防火墙控制机和代理机在同一子网控制机和代理机上安装的jmeter和JDK版本要一样关闭jmeter的RMI SSL开关 二 代理机&#xff08;agent&#xff09;的配置 修改服务端口 打开bin/jmeter.properties文件&#xff0c;修改’server_port’ 将RMI SSL设备…...

[华为杯研究生创新赛 2023] 初赛 REV WP

前言 一年没打比赛了, 差一题进决赛, REV当时lin的第三个challenge没看出来是凯撒, 想得复杂了, 结果错失一次线下机会 >_< T4ee 动态调试, nop掉反调试代码 发现处理过程为 置换sub_412F20处理(这里看其他师傅的wp知道应该是rc4, 我是直接en逆的buf字符串中每一位和…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...