309. 买卖股票的最佳时机含冷冻期(leetcode) 动态规划思想
文章目录
- 前言
- 一、题目分析
- 二、算法原理
- 1.状态表示
- 2.状态转移方程
- 3.初始化+边界条件
- 4.填表顺序
- 5.返回值是什么
- 三、代码实现
- 总结
前言
在本文章中,我们将要详细介绍一下Leetcode中买卖股票的最佳时机含冷冻期相关的内容,本题采用动态规划的思想解决
一、题目分析

二、算法原理
1.状态表示
列出dp表,dp表中值的含义是什么
dp[i]表示第i天之后此时的最大利润
由于第i天不确定具体状态,多状态dp问题
🌟 .dp[i][0]:手中有股票没有卖出,我们简单称为买入状态,此时的最大利润
🌟 .dp[i][1]:处于冷冻期,无法购买股票,我们称为冷冻期,此时的最大利润
🌟 .dp[i][2]:手中没有股票,也不处于冷冻期,此时的最大利润
2.状态转移方程
根据最近一步划分问题
根据状态表示,我们可以划分为9种不同的转换
🌟 .(i-1)天处于买入状态,第i天处于买入状态:这个是可以的,这一天啥也不干
🌟 .(i-1)天处于买入状态,第i天处于冷冻期状态:这个可以,就是这天把股票卖了,赚了钱,需要加上prices[i]的值(涉及利润)
🌟 .(i-1)天处于买入状态,第i天处于正常状态:这个不可以,你手中有股票,不处于正常状态,即使把股票卖了,也得先经过冷冻期才可以
🌟 .(i-1)天处于冷冻期状态,第i天处于冷冻期状态:这个不可以,冷冻期只能有一天
🌟 .(i-1)天处于冷冻期状态,第i天处于买入状态:这个不可以,冷冻期是不能买股票的
🌟 .(i-1)天处于冷冻期状态,第i天处于正常状态:这个可以,经过一天之后进入正常状态。
🌟 .(i-1)天处于正常状态,第i天处于正常状态:这个可以,感觉这个股票不好,等一等再买
🌟 .(i-1)天处于正常状态,第i天处于买入状态:这个可以,可以进行购买股票,买股票需要花钱,需要减去股票的钱pricesi
🌟 .(i-1)天处于正常状态,第i天处于冷冻期状态:这个不可以,冷冻期是在股票卖了之后才进入的
下面有个简图描述上面信息

箭头方向表示:从(i-1)天到第i天
3.初始化+边界条件
本题初始化比较简单,不需要创建虚拟节点了
dp[0][0]=-prices[0];这一天只买了股票,买是需要花钱的
dp[0][1]=0;买了有紧接着卖了,没有利润
dp[0][2]=0;
4.填表顺序
从左往右
5.返回值是什么
最后一天的最大收益有两种可能,而且一定是“不持有”状态下的两种可能,把这两种“不持有”比较一下大小,返回即可
max(dp[n-1][1],dp[n–1][2]);
三、代码实现
class Solution {
public:int maxProfit(vector<int>& prices) {//建表int n=prices.size();if(n==0){return 0;}vector<vector<int>>dp (n,vector<int>(3));//初始化dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=0;//填表for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);dp[i][1]=dp[i-1][0]+prices[i];dp[i][2]=max(dp[i-1][2],dp[i-1][1]);}//返回值return max(dp[n-1][1],dp[n-1][2]);}
};

总结
以上就是我们对本题详细介绍,希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~😘😘😘😘
相关文章:
309. 买卖股票的最佳时机含冷冻期(leetcode) 动态规划思想
文章目录 前言一、题目分析二、算法原理1.状态表示2.状态转移方程3.初始化边界条件4.填表顺序5.返回值是什么 三、代码实现总结 前言 在本文章中,我们将要详细介绍一下Leetcode中买卖股票的最佳时机含冷冻期相关的内容,本题采用动态规划的思想解决 一、…...
3D渲染和动画制作软件KeyShot Pro mac附加功能
KeyShot 11 mac是一款专业化实时3D渲染工具,使用它可以简化3d渲染和动画制作流程,并且提供最准确的材质及光线,渲染效果更加真实,KeyShot为您提供了使用 CPU 或 NVIDIA GPU 进行渲染的能力和选择,并能够线性扩展以获得…...
集合的几个遍历方法
1. 集合的遍历 1.0 创建集合代码 List<String> strList new ArrayList<>(); strList.add("huawei"); strList.add("xiaomi"); strList.add("tencent"); strList.add("google"); strList.add("baidu");1.1 fo…...
【使用apache snakeyaml 管理yml文件】
使用apache snakeyaml 管理yml文件 1. 一个Yaml工厂2.Yaml工具类3. 测试类4. 完成 ! OK 1. 一个Yaml工厂 public class YamlFactory {public static YamlUtil get(){return new YamlUtil();} }2.Yaml工具类 Slf4j public class YamlUtil {private Yaml yaml;publi…...
uniapp - 简单版本自定义tab栏切换
tab切换是APP开发最常见的功能之一,uniapp中提供了多种形式的tab组件供我们使用。对于简单的页面而言,使用tabbar组件非常方便快捷,可以快速实现底部导航栏的效果。对于比较复杂的页面,我们可以使用tab组件自由定义样式和内容 目录…...
工作中常用的RabbitMQ实践
目录 1.前置知识 准备工作 2.导入依赖 3.生产者 4.消费者 5.验证 验证Direct 验证Fanout 验证Topic 1.前置知识 rabbitmq有五种工作模式;按照有无交换机分为两大类 无交换机的:简单队列(一对一,单生产单消费)、工作队列(工作队列有轮训分发和公…...
程序员常用英文单词
英语对于程序员来说多么重要应该无需过多解释了,把近期在网上收集到的分享到这里供大家学习交流。 PS:感谢原作者的收集,谢谢。 A abstract 抽象的 abstract base class (ABC) 抽象基类abstract class 抽象类 abstraction 抽象、抽象物、抽象…...
QStringListModel 是 Qt 框架中用于在模型-视图(Model-View)架构中展示字符串列表的类
QStringListModel 是 Qt 框架中用于在模型-视图(Model-View)架构中展示字符串列表的类。 QStringListModel 继承自 QAbstractListModel,是一个基于字符串列表的数据模型。它提供了一种方便的方式来将字符串列表作为数据源,供各种…...
vue使用echarts显示中国地图
项目引入echarts以后,在页面创建canvas标签 引入一个公共js文件(下面这段代码就是china.js文件) (function (root, factory) {if (typeof define function && define.amd) {// AMD. Register as an anonymous module.define([ex…...
ATM的转账
【 1 】明确我们要实现的功能 # 用户功能菜单 # 1.注册 # 2.登陆 # 3.取款 # 4.转账 # 5.充值余额 # 6.查看流水 # 7.查看银行信息(查看自己…...
在Windows 10或11中,复制和粘贴不起作用,不一定是键盘的问题
以下建议将帮助你解决复制和粘贴无法正常工作的问题。 以下提示主要适用于Windows 10和Windows 11,但也可能解决旧版本Windows上的复制和粘贴问题。 为什么我的复制粘贴不起作用 复制和粘贴不起作用的问题可能以以下方式之一出现。 其他正在运行的应用程序或进程可能会使用…...
git 使用记录
远程仓库为空初始化 初始化本地仓库 git init 在本地仓库书写代码(这里可以编辑一个文本文件做测试,如hello.txt) 5)执行:git add 要让git管理的文件(git add hello.txt)>执行完此操作将我…...
支持大模型训练的计算机系统
摘要: 训练数据决定了基础大模型可用的理论信息,模型架构和训练目标决定了可以提取多少信息,计算机系统决定了实际可实现的内容。在数据和模型大小方面,系统是扩展的关键瓶颈,这两者似乎都可以可靠地跟踪能力的改进。在…...
SAP ABAP-AVL-OO方法中的ALV的如何自己添加按钮及其响应
ABAP-AVL-OO方法中的ALV的如何自己添加按钮及其响应 SAP在做报表开发中,不同公司对报表的风格往往各异,为此经常在使用OO方法做ALV报表中需要去掉自带的工具栏而自行添加一些工具按钮,下面将简单介绍一下添加按钮及如何响应的实现方法&#…...
uniapp移动端悬浮按钮(吸附边缘)
Uniapp移动端悬浮按钮可以通过CSS实现吸附边缘的效果。具体实现步骤如下: html: <movable-area class"movable-area"><movable-view class"movable-view" :position"position" :x"x" :y"y"…...
【成功】Linux安装Mysql8并设置远程连接
今天在新搞来的阿里云的服务器里安装MySQL8,记录一下过程: 这是MySQL的官网和下载地址:MySQL :: Download MySQL Community Server (Archived Versions) 1. 先进入安装目录 cd /usr/local 2. 安装 wget https://downloads.mysql.com/arch…...
高效纯化树脂A-2313 CPR
在化工、制药等行业中,对colorful chemicals的纯化一直是挑战。本文将为您介绍一款具有卓越性能的强碱性阴离子交换树脂——Tulsion A-2313 CPR。通过分析其特性和应用,展示其在colorful chemicals纯化领域的优势。 一、Tulsion A-2313 CPR离子交换树脂的…...
uni-app实现安卓原生态调用身份证阅读器读卡库读身份证和社保卡、银行卡、IC卡等功能
DONSEE系列多功能读写器Android Uniapp API接口规范V1.0.0 本项目Uniapp调用了身份证读卡器的库文件:DonseeDeviceLib-debug.aar,该库放到nativeplugins\donsee-card\android,然后会自动加载。SDK会自动检查是否拥有USB设备权限,…...
【QT】QComboBox和QPlainTextEdit基本介绍和应用示例
目录 1.QComboBox 1.1 QComboBox概述 1.2 QComboBox信号 1.3 QComboBox常用功能 1.4 QComboBox添加简单项 1.6 QComboBox列表项的访问 2.QPlainTextEdit 2.1 QPlainTextEdit概述 2.2 QPlainTextEdit的基本属性 2.3 QPlainTextEdit的公共函数 2.4 QPlainTextEdit的公…...
Path的使用-path绘制折线的时候带上圆角
场景: 使用antv-g6 自定义边的时候,绘制折线,此时都是直角,需要加圆角,没找到属性,自己绘制: 最后使用了A(elliptical Arc)弧形 A命令用于画弧形。 A rx ry x-axis-r…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...
图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...
[特殊字符] 手撸 Redis 互斥锁那些坑
📖 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作,想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁,也顺便跟 Redisson 的 RLock 机制对比了下,记录一波,别踩我踩过…...
