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

代码随想录算法训练营Day51 | 309. 最佳买卖股票时机含冷冻期 | 714. 买卖股票的最佳时机含手续费 | 股票总结

文章目录

  • 309. 最佳买卖股票时机含冷冻期
    • 标准 dp
    • 机智的分析解法
  • 714. 买卖股票的最佳时机含手续费
    • 贪心算法
  • 股票总结

309. 最佳买卖股票时机含冷冻期

题目链接 | 解题思路

标准 dp

本题多了冷却期的条件,将原本的两个状态变得更复杂了。变化在于,如果考虑第 i 天的状态是“持有股票”,那么不能简单地推导为“第 i-1 天持有股票”和“第 i-1 天未持有股票,第 i 天买入股票”,因为可能第 i 天是冷却期。所以,需要特殊讨论针对冷却期的递推公式。

可以看到和之前的一个最大的区别在于,本题需要详细地分类讨论“不持有股票的状态”。每一天的情况可能是“持有股票”,“未持有股票 + 不在冷却期”,“未持有股票 + 在冷却期”,“未持有股票 + 刚卖出股票”。分类讨论的情况更多了,需要更清晰的递推公式。另外,本题还单独列出了“今天刚卖出股票”这个具体的动作状态,是因为“刚卖出股票” -> “冷却期”这个递推是确定的。

  1. dp 数组的下标含义:
    • dp[i][0]:第 i 天结束时持有股票
    • dp[i][1]:第 i 天结束时不持有股票 + 不在冷却期内
    • dp[i][2]:第 i 天结束时不持有股票 + 当天卖出股票
    • dp[i][3]:第 i 天结束时不持有股票 + 当天为冷却期
  2. 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 天必然是卖出股票的
  3. dp 数组的初始化:初始化自然是考虑第一天,本题的初始化还是有些难判断的
    • dp[0][0] = -prices[0]:显然,第一天结束时持有股票,那只能是第一天购买了股票
    • dp[0][1] = 0:显然,第一天结束时没有持有股票,只能是第一天没有任何操作
    • dp[0][2] = 0:符合定义的话,只能是第一天就买入再卖出股票,收益为 0
    • dp[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
  4. dp 的遍历顺序:从前向后即可。
  5. 举例推导:
12302
0-1-1-111
100012
2012-13
30012-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 本题多了冷却期的条件&#xff0c;将原本的两个状态变得更复杂了。变化在于&#xff0c;如果…...

C#,《小白学程序》第八课:列表(List)应用之二“编制高铁列车时刻表”

1 文本格式 /// <summary> /// 车站信息类 class /// </summary> public class Station { /// <summary> /// 编号 /// </summary> public int Id { get; set; } 0; /// <summary> /// 车站名 /// </summary&g…...

2、QT的信号与槽

一、什么是信号与槽 一个对象发送一个信号出去&#xff0c;另外一个对象接收到该信号后&#xff0c;会触发相应的槽函数 二、信号与槽的语法 connect(信号的发送者&#xff0c;SIGNAL(信号名称),信号的接收者,SLOT(槽函数)); 1、写法&#xff1a; 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)

前言&#xff1a;每日一练系列&#xff0c;每一期都包含5道选择题&#xff0c;2道编程题&#xff0c;博主会尽可能详细地进行讲解&#xff0c;令初学者也能听的清晰。每日一练系列会持续更新&#xff0c;上学期间将看学业情况更新。 五道选择题&#xff1a; 1、程序运行的结果…...

H5 + C3基础(六)(2D转换transform 位移 旋转 缩放)

2D转换transform & 2D转换transform平移利用平移百分比优化盒子水平垂直居中 旋转指定2d变换的中心点 transform-origin 缩放2d转换简写 2D转换transform 所谓2D转换&#xff0c;就是在二维坐标系内进行各种操作&#xff0c;包括平移&#xff0c;转动&#xff0c;缩放等等…...

2023最新 Electron.js 桌面应用开发教程(基础篇)更新中

Electron是什么&#xff1f; 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是一个传输层协议&#xff0c;用于ZMQ的连接的信息交互&#xff0c;本文档描述的是3.0协议&#xff0c;主要分析基于NULL Security Mechanism 协议语法 ZMTP由三部分组成&#xff0c;分别是 greeting、handshake、traffic 部分描述构成greeting描述…...

ubuntu18安装中文环境

1. 安装中文语言包 首先&#xff0c;我们需要安装中文语言包。打开终端&#xff0c;输入以下命令&#xff1a; sudo apt-get install language-pack-zh-hans 这个命令会下载并安装中文语言包。安装完成后&#xff0c;我们需要重新启动系统(reboot)。 2. 安装中文输入法 安…...

怎么提取视频中的音乐保存到本地?其实方法很简单

当你想要使用视频中的音乐时&#xff0c;你可以考虑将它从视频中提取出来。这可以用于制作音频样本集&#xff0c;制作铃声或其他音频素材&#xff0c;或者向其他人展示视频的音乐部分而无需显示视频本身。如果你是一位音乐制作人员&#xff0c;你可能会需要一些特定类型的音效…...

线性代数的学习和整理18:矩阵的秩的各种定理, 秩和维度(未完成)

目录 1 矩阵的秩 矩阵的秩 2 求秩的方法 矩阵的维度秩 矩阵的维度 向量的模&#xff0c;矩阵的模-没有把&#xff0c;难道是面积&#xff1f; 矩阵的平直概念 5 矩阵的初等变换&#xff08;矩阵等价概念的引出&#xff09; 1 为什么要引入矩阵的“秩” 这个概念&#x…...

UVa11374 Airport Express(Dijkstra)

题意 给出经济路线以及商业路线&#xff0c;在给出起始点s&#xff0c;终止点e&#xff0c;在只能使用其中一个商业路线 的情况下输出最短路径 思路 如果选择商业路线为从u到v&#xff0c;则需要从s->u,u->v&#xff0c;v->e点的路径最短。使用Dijkstra计算出从s点…...

hadoop的hdfs中避免因节点掉线产生网络风暴

hadoop的hdfs中避免因节点掉线产生网络风暴 控制节点掉线RPC风暴的参数 三个参数都是hdfs-site.xml中参数&#xff0c;具体可以参考apache hadoop官网&#xff0c;其实块的复制速度有两个方面决定&#xff0c;一是namenode分发任务的速度&#xff0c;二则是datanode之间进行复…...

2023年高教社杯 国赛数学建模思路 - 案例:最短时间生产计划安排

文章目录 0 赛题思路1 模型描述2 实例2.1 问题描述2.2 数学模型2.2.1 模型流程2.2.2 符号约定2.2.3 求解模型 2.3 相关代码2.4 模型求解结果 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 最短时…...

Spring MVC介绍

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

5年测试在职经验之谈:2年功能测试、3年自动化测试,从入门到不可自拔...

毕业3年了&#xff0c;学的是环境工程专业&#xff0c;毕业后零基础转行做软件测试。 已近从事测试行业8年了&#xff0c;自己也从事过2年的手工测试&#xff0c;从事期间越来越觉得如果一直在手工测试的道路上前进&#xff0c;并不会有很大的发展&#xff0c;所以通过自己的努…...

【Python数据分析】数据分析之numpy基础

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

Swift 如何从图片数据(Data)检测原图片类型?

功能需求 如果我们之前把图片对应的数据(Data)保持在内存或数据库中,那么怎么从 Data 对象检测出原来图片的类型呢? 如上图所示:我们将 11 张不同类型的图片转换为 Data 数据,然后从 Data 对象正确检测出了原图片类型。 目前,我们的代码可以检测出 jpeg(jpg), tiff,…...

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

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

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战

🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...

项目进度管理软件是什么?项目进度管理软件有哪些核心功能?

无论是建筑施工、软件开发&#xff0c;还是市场营销活动&#xff0c;项目往往涉及多个团队、大量资源和严格的时间表。如果没有一个系统化的工具来跟踪和管理这些元素&#xff0c;项目很容易陷入混乱&#xff0c;导致进度延误、成本超支&#xff0c;甚至失败。 项目进度管理软…...

Angular中Webpack与ngx-build-plus 浅学

Webpack 在 Angular 中的概念 Webpack 是一个模块打包工具&#xff0c;用于将多个模块和资源打包成一个或多个文件。在 Angular 项目中&#xff0c;Webpack 负责将 TypeScript、HTML、CSS 等文件打包成浏览器可以理解的 JavaScript 文件。Angular CLI 默认使用 Webpack 进行项目…...

可下载旧版app屏蔽更新的app市场

软件介绍 手机用久了&#xff0c;app越来越臃肿&#xff0c;老手机卡顿成常态。这里给大家推荐个改善老手机使用体验的方法&#xff0c;还能帮我们卸载不需要的app。 手机现状 如今的app不断更新&#xff0c;看似在优化&#xff0c;实则内存占用越来越大&#xff0c;对手机性…...

android关于pthread的使用过程

文章目录 简介代码流程pthread使用hello_test.cppAndroid.bp 编译过程报错处理验证过程 简介 android开发经常需要使用pthread来编写代码实现相关的业务需求 代码流程 pthread使用 需要查询某个linux函数的方法使用&#xff0c;可以使用man 函数名 // $ man pthread_crea…...