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…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
ZYNQ学习记录FPGA(二)Verilog语言
一、Verilog简介 1.1 HDL(Hardware Description language) 在解释HDL之前,先来了解一下数字系统设计的流程:逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端,在这个过程中就需要用到HDL,正文…...
