代码随想录算法训练营Day51 | 309. 最佳买卖股票时机含冷冻期 | 714. 买卖股票的最佳时机含手续费 | 股票总结
文章目录
- 309. 最佳买卖股票时机含冷冻期
- 标准 dp
- 机智的分析解法
- 714. 买卖股票的最佳时机含手续费
- 贪心算法
- 股票总结
309. 最佳买卖股票时机含冷冻期
题目链接 | 解题思路
标准 dp
本题多了冷却期的条件,将原本的两个状态变得更复杂了。变化在于,如果考虑第 i
天的状态是“持有股票”,那么不能简单地推导为“第 i-1
天持有股票”和“第 i-1
天未持有股票,第 i
天买入股票”,因为可能第 i
天是冷却期。所以,需要特殊讨论针对冷却期的递推公式。
可以看到和之前的一个最大的区别在于,本题需要详细地分类讨论“不持有股票的状态”。每一天的情况可能是“持有股票”,“未持有股票 + 不在冷却期”,“未持有股票 + 在冷却期”,“未持有股票 + 刚卖出股票”。分类讨论的情况更多了,需要更清晰的递推公式。另外,本题还单独列出了“今天刚卖出股票”这个具体的动作状态,是因为“刚卖出股票” -> “冷却期”这个递推是确定的。
- dp 数组的下标含义:
dp[i][0]
:第i
天结束时持有股票dp[i][1]
:第i
天结束时不持有股票 + 不在冷却期内dp[i][2]
:第i
天结束时不持有股票 + 当天卖出股票dp[i][3]
:第i
天结束时不持有股票 + 当天为冷却期
- dp 递推公式:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] - prices[i])
,如果第i
天持有股票,那么- 第
i-1
天就持有股票,dp[i][0] = dp[i-1][0]
- 第
i-1
天不持有股票,那又分为两种情况- 第
i-1
天是冷却期,第i
天可以正常交易,dp[i][0] = dp[i-1][3]
- 第
i-1
天不在冷却期内,第i
天可以正常交易,dp[i][0] = dp[i-1][1]
- 第
- 第
dp[i][1] = max(dp[i-1][1], dp[i-1][3])
,如果第i
天不是冷却期,那么- 第
i-1
天就不在冷却期,dp[i][1] = dp[i-1][1]
- 第
i-1
天就是冷却期,dp[i][1] = dp[i-1][3]
- 第
dp[i][2] = dp[i-1][0] + prices[i]
,如果第i
天要卖出股票,那么第i-1
天必然是持有股票的dp[i][3] = dp[i-1][2]
,如果第i
天是冷却期,那么第i-1
天必然是卖出股票的
- dp 数组的初始化:初始化自然是考虑第一天,本题的初始化还是有些难判断的
dp[0][0] = -prices[0]
:显然,第一天结束时持有股票,那只能是第一天购买了股票dp[0][1] = 0
:显然,第一天结束时没有持有股票,只能是第一天没有任何操作dp[0][2] = 0
:符合定义的话,只能是第一天就买入再卖出股票,收益为 0dp[0][3] = 0
:根据定义,这个状态是非法的,因为很明显不可能在第一天就进入冷却期(没有办法在前一天卖出股票)。然而定义上非法的初始化,也要为了后续的递推服务,所以可以根据递推公式来得到初始化的值:- 在第二天的状态中,只有
dp[1][1] = max(dp[0][1], dp[0][3])
会用到dp[0][3]
。从含义上,第二天如果不持有股票并且不在冷却期,那么第一天就肯定没有买入股票,dp[1][1]
应该是 0(dp[0][1]
)。那么为了得到正确的dp[1][1]
,我们应该初始化dp[0][3] = 0
。
- 在第二天的状态中,只有
- dp 的遍历顺序:从前向后即可。
- 举例推导:
1 | 2 | 3 | 0 | 2 | |
---|---|---|---|---|---|
0 | -1 | -1 | -1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 2 |
2 | 0 | 1 | 2 | -1 | 3 |
3 | 0 | 0 | 1 | 2 | -1 |
class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) == 1:return 0dp = [[0] * 4 for _ in range(len(prices))]dp[0][0] = -prices[0]for i in range(1, len(prices)):dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] - prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][3])dp[i][2] = dp[i-1][0] + prices[i]dp[i][3] = dp[i-1][2]return max(dp[-1][1], dp[-1][2], dp[-1][3])
和之前一样,也可以优化成 O ( 1 ) O(1) O(1) 的空间复杂度。
机智的分析解法
本题和122. 买卖股票的最佳时机II的区别只在于多了一个冷却期。如上的状态分析是解决题目的标准流程。但是延续之前题目的做法,同样也能解决这道题。注意到,不持有股票的状态不会受到任何影响,只有想要买入股票的时候需要考虑冷却期的存在。
关键在于:“如果第 i
天持有股票,那么当前的收益究竟怎么进行推导”
- 如果第
i - 1
天就持有股票,那么就直接复制前一天的状态,dp[i][1] = dp[i-1][1]
- 如果第
i - 1
天未持有股票,那么分两种情况:- 第
i - 1
天是冷却期,那么就是在第i - 2
天卖出了股票,dp[i][1] = dp[i-2][0] - prices[i]
- 第
i - 1
天不是冷却期,那么应该得到dp[i][1] = dp[i-1][0] - prices[i]
- 第
如果根据以上的状态分析,无法得到一个 closed-form 的递推公式,因为我们不知道第 i-1
天是否是冷却期,也就不知道何时该使用 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
,何时该使用 dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
。
但是,如果第 i-1
天不是冷却期且不持有股票,那么第 i-1
天只有两种情况:
- 之前从来没有交易过股票
- 第
i - 2
天或之前是冷却期
无论是哪种情况,我们都能得到 dp[i-1][0] = dp[i-2][0]
。所以虽然第 i-1
天的状态是否是冷却期不得而知,但是第 i
天持有股票的递推公式可以确定是 dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
。
这样,我们只需要最小限度地修改122. 买卖股票的最佳时机II的代码,就能解题。
class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) == 1:return 0# dp[i][0] represents the max profit on day i without the stock# dp[i][1] represents the max profit on day i with the stockdp = [[0, 0] for _ in range(len(prices))]dp[0] = [0, -prices[0]]dp[1] = [max(0, prices[1] - prices[0]), max(-prices[0], -prices[1])]for i in range(2, len(prices)):dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])return dp[-1][0]
714. 买卖股票的最佳时机含手续费
题目链接 | 解题思路
本题的 dp 解法和122. 买卖股票的最佳时机II唯一的区别是多了一个手续费,所以从“持有股票”到“未持有股票”的利润递推需要多减去手续费,其他全部保持不变。
class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:# dp[i][0] represents the max profit on day i without the stock# dp[i][1] represents the max profit on day i with the stockdp = [[0, 0] for _ in range(len(prices))]dp[0] = [0, -prices[0]]for i in range(1, len(prices)):dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])return dp[-1][0]
贪心算法
贪心解法
本题也可以用贪心算法来解决,也算是照应了122. 买卖股票的最佳时机II。但是本题的贪心解法不像之前一样简单,在计算的时候对所需要的区间要求更高,情况也更复杂。
如果简单计算所有增区间,那么就会遇到有的区间利润不足以抵手续费的情况,同时多次买卖也会导致更多的手续费,从而使利润降低。所以我们想找到的区间,应该是:
- 买入利润:遇到更低的价格就更新记录;
- 卖出利润:按理来说是当前增最大区间的最后一天的利润。但是没必要具体知道哪一天进行了卖出,只要当能够盈利的时候进行一次模拟的卖出即可,同样能够得到正确的利润(但是需要一些小技巧)。
如下,在第一次发现当前的交易能够制造利润时(prices[i] > min_price + fee
),我们会选择直接进行当前交易,并且扣除一次手续费,随后减少 min_price
。之后会有两种情况:假设 fee = 2
,
prices = [1, 4, 0, 5]
:- 第二天,发现有真正的盈利,
profit = 1, min_price = 2
- 第三天,发现了更低的价格,
min_price = 0
,将会开始新的交易,同时结束了上一次的交易(记录区间)
- 第二天,发现有真正的盈利,
prices = [1, 5, 8]
:- 第二天,发现有真正的盈利,
profit = 2, min_price = 3
- 第三天,发现有真正的盈利,此时新的盈利为5,而不是预计的3,因为
min_price
在这次计算前发生了变化,相当于抵消了该次交易的手续费
- 第二天,发现有真正的盈利,
所以模拟的卖出实际上是在第一次发现真正的盈利后,就记录一次交易的手续费,并且改变当前的 min_price
,从而免除当前区间的后续交易(如果存在)的手续费。着实非常巧妙!
class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:min_price = prices[0]profit = 0for i in range(1, len(prices)):if prices[i] < min_price:min_price = prices[i]if prices[i] <= prices[i] <= min_price + fee:continueif prices[i] > min_price + fee:profit += (prices[i] - min_price) - feemin_price = prices[i] - feereturn profit
股票总结
股票问题总结
股票问题是第一次在 dp 中需要记录状态的题型。之前的 dp 题,无论是打家劫舍还是背包问题,都是考验对子问题最优解的利用,即正确的递推公式+遍历顺序。股票问题则需要对子问题进行分类讨论,记录各个状态下的子问题最优解,这一点是非常新颖的。同时,不知道是不是巧合,大部分股票问题都可以用贪心来解决,虽然实现贪心的难度不小。
最标准的股票问题应该是122. 买卖股票的最佳时机II,需要真正地记录并利用状态。
随后,复杂的限制交易次数的股票问题188.买卖股票的最佳时机IV把 dp 变得更复杂了,相比于之前的标准题,有了类似爬楼梯式的进阶。
而堪称神题的是309.最佳买卖股票时机含冷冻期。标准解法中,活用了状态分类的思想,将原本的“未持有股票”进一步细分,来适应新条件下的递推公式。而机智的分析算法中,通过分析最小限度地修改了之前的代码,解决了问题。两种解法都非常重要,代表了股票问题的精华。
相关文章:
代码随想录算法训练营Day51 | 309. 最佳买卖股票时机含冷冻期 | 714. 买卖股票的最佳时机含手续费 | 股票总结
文章目录 309. 最佳买卖股票时机含冷冻期标准 dp机智的分析解法 714. 买卖股票的最佳时机含手续费贪心算法 股票总结 309. 最佳买卖股票时机含冷冻期 题目链接 | 解题思路 标准 dp 本题多了冷却期的条件,将原本的两个状态变得更复杂了。变化在于,如果…...

C#,《小白学程序》第八课:列表(List)应用之二“编制高铁列车时刻表”
1 文本格式 /// <summary> /// 车站信息类 class /// </summary> public class Station { /// <summary> /// 编号 /// </summary> public int Id { get; set; } 0; /// <summary> /// 车站名 /// </summary&g…...

2、QT的信号与槽
一、什么是信号与槽 一个对象发送一个信号出去,另外一个对象接收到该信号后,会触发相应的槽函数 二、信号与槽的语法 connect(信号的发送者,SIGNAL(信号名称),信号的接收者,SLOT(槽函数)); 1、写法: QT 4 的写法 connect(sende…...

Java代码审计15之Apache log4j2漏洞
文章目录 1、log4j简介2、复现2.1、高版本测试2.2、测试代码2.3、补充之dns探测2.3.1、rmi、ldap也可以dnslog探测 2.3.2、dnslog外带信息 3、漏洞原理3.1、漏洞的危害大的背景3.2、具体的代码调试 4、靶场测试4.1、dns探测4.2、工具下载与使用4.3、测试4.4、手工可以测出&…...

c语言每日一练(13)
前言:每日一练系列,每一期都包含5道选择题,2道编程题,博主会尽可能详细地进行讲解,令初学者也能听的清晰。每日一练系列会持续更新,上学期间将看学业情况更新。 五道选择题: 1、程序运行的结果…...
H5 + C3基础(六)(2D转换transform 位移 旋转 缩放)
2D转换transform & 2D转换transform平移利用平移百分比优化盒子水平垂直居中 旋转指定2d变换的中心点 transform-origin 缩放2d转换简写 2D转换transform 所谓2D转换,就是在二维坐标系内进行各种操作,包括平移,转动,缩放等等…...

2023最新 Electron.js 桌面应用开发教程(基础篇)更新中
Electron是什么? Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 嵌入 Chromium 和 Node.js 到 二进制的 Electron 允许您保持一个 JavaScript 代码代码库并创建 在Windows上运行的跨平台应用 macOS和Linux Electron Fiddle 运行实例 Ele…...

【ES】笔记-Set集合实践
JS <script>let arr[1,2,3,4,5,4,3,2,1];//1.数组去重let result0[...new Set(arr)];console.log(数组去重${result0});//2.交集let arr2[4,5,6,5,6];let result[...new Set(arr)].filter(item>{let s2new Set(arr2);//4 5 6if(s2.has(item)){return true;}else{retur…...

缺陷或负样本难以收集怎么办?使用生成式模型自动生成训练样本,image-to-image Stable diffusion
文章大纲 样本稀疏与对应的解决方案如何解决工业缺陷检测小样本问题参考1:AIDG(Artificial Intelligent Defect Generator)参考2:灵感来源 : Image-to-Image Diffusion Models参考文献与学习路径参考博文数据集算法缺陷检测库hugging face样本稀疏与对应的解决方案 1.数据层面…...

ZMTP协议
ZoreMQ Transport Protocol是一个传输层协议,用于ZMQ的连接的信息交互,本文档描述的是3.0协议,主要分析基于NULL Security Mechanism 协议语法 ZMTP由三部分组成,分别是 greeting、handshake、traffic 部分描述构成greeting描述…...
ubuntu18安装中文环境
1. 安装中文语言包 首先,我们需要安装中文语言包。打开终端,输入以下命令: sudo apt-get install language-pack-zh-hans 这个命令会下载并安装中文语言包。安装完成后,我们需要重新启动系统(reboot)。 2. 安装中文输入法 安…...

怎么提取视频中的音乐保存到本地?其实方法很简单
当你想要使用视频中的音乐时,你可以考虑将它从视频中提取出来。这可以用于制作音频样本集,制作铃声或其他音频素材,或者向其他人展示视频的音乐部分而无需显示视频本身。如果你是一位音乐制作人员,你可能会需要一些特定类型的音效…...

线性代数的学习和整理18:矩阵的秩的各种定理, 秩和维度(未完成)
目录 1 矩阵的秩 矩阵的秩 2 求秩的方法 矩阵的维度秩 矩阵的维度 向量的模,矩阵的模-没有把,难道是面积? 矩阵的平直概念 5 矩阵的初等变换(矩阵等价概念的引出) 1 为什么要引入矩阵的“秩” 这个概念&#x…...
UVa11374 Airport Express(Dijkstra)
题意 给出经济路线以及商业路线,在给出起始点s,终止点e,在只能使用其中一个商业路线 的情况下输出最短路径 思路 如果选择商业路线为从u到v,则需要从s->u,u->v,v->e点的路径最短。使用Dijkstra计算出从s点…...
hadoop的hdfs中避免因节点掉线产生网络风暴
hadoop的hdfs中避免因节点掉线产生网络风暴 控制节点掉线RPC风暴的参数 三个参数都是hdfs-site.xml中参数,具体可以参考apache hadoop官网,其实块的复制速度有两个方面决定,一是namenode分发任务的速度,二则是datanode之间进行复…...

2023年高教社杯 国赛数学建模思路 - 案例:最短时间生产计划安排
文章目录 0 赛题思路1 模型描述2 实例2.1 问题描述2.2 数学模型2.2.1 模型流程2.2.2 符号约定2.2.3 求解模型 2.3 相关代码2.4 模型求解结果 建模资料 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 最短时…...

Spring MVC介绍
MVC模式是什么 MVC 模式,全称为 Model-View-Controller(模型-视图-控制器)模式,它是一种软件架构模式,其目标是将软件的用户界面(即前台页面)和业务逻辑分离,使代码具有更高的可扩展…...

5年测试在职经验之谈:2年功能测试、3年自动化测试,从入门到不可自拔...
毕业3年了,学的是环境工程专业,毕业后零基础转行做软件测试。 已近从事测试行业8年了,自己也从事过2年的手工测试,从事期间越来越觉得如果一直在手工测试的道路上前进,并不会有很大的发展,所以通过自己的努…...

【Python数据分析】数据分析之numpy基础
实验环境:建立在Python3的基础之上 numpy提供了一种数据类型,提供了数据分析的运算基础,安装方式 pip install numpy导入numpy到python项目 import numpy as np本文以案例的方式展示numpy的基本语法,没有介绍语法的细枝末节&am…...

Swift 如何从图片数据(Data)检测原图片类型?
功能需求 如果我们之前把图片对应的数据(Data)保持在内存或数据库中,那么怎么从 Data 对象检测出原来图片的类型呢? 如上图所示:我们将 11 张不同类型的图片转换为 Data 数据,然后从 Data 对象正确检测出了原图片类型。 目前,我们的代码可以检测出 jpeg(jpg), tiff,…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...