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

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.返回值是什么 三、代码实现总结 前言 在本文章中&#xff0c;我们将要详细介绍一下Leetcode中买卖股票的最佳时机含冷冻期相关的内容&#xff0c;本题采用动态规划的思想解决 一、…...

3D渲染和动画制作软件KeyShot Pro mac附加功能

KeyShot 11 mac是一款专业化实时3D渲染工具&#xff0c;使用它可以简化3d渲染和动画制作流程&#xff0c;并且提供最准确的材质及光线&#xff0c;渲染效果更加真实&#xff0c;KeyShot为您提供了使用 CPU 或 NVIDIA GPU 进行渲染的能力和选择&#xff0c;并能够线性扩展以获得…...

集合的几个遍历方法

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. 完成 &#xff01; 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开发最常见的功能之一&#xff0c;uniapp中提供了多种形式的tab组件供我们使用。对于简单的页面而言&#xff0c;使用tabbar组件非常方便快捷&#xff0c;可以快速实现底部导航栏的效果。对于比较复杂的页面&#xff0c;我们可以使用tab组件自由定义样式和内容 目录…...

工作中常用的RabbitMQ实践

目录 1.前置知识 准备工作 2.导入依赖 3.生产者 4.消费者 5.验证 验证Direct 验证Fanout 验证Topic 1.前置知识 rabbitmq有五种工作模式&#xff1b;按照有无交换机分为两大类 无交换机的&#xff1a;简单队列(一对一,单生产单消费)、工作队列(工作队列有轮训分发和公…...

程序员常用英文单词

英语对于程序员来说多么重要应该无需过多解释了&#xff0c;把近期在网上收集到的分享到这里供大家学习交流。 PS&#xff1a;感谢原作者的收集&#xff0c;谢谢。 A abstract 抽象的 abstract base class (ABC) 抽象基类abstract class 抽象类 abstraction 抽象、抽象物、抽象…...

QStringListModel 是 Qt 框架中用于在模型-视图(Model-View)架构中展示字符串列表的类

QStringListModel 是 Qt 框架中用于在模型-视图&#xff08;Model-View&#xff09;架构中展示字符串列表的类。 QStringListModel 继承自 QAbstractListModel&#xff0c;是一个基于字符串列表的数据模型。它提供了一种方便的方式来将字符串列表作为数据源&#xff0c;供各种…...

vue使用echarts显示中国地图

项目引入echarts以后&#xff0c;在页面创建canvas标签 引入一个公共js文件&#xff08;下面这段代码就是china.js文件&#xff09; (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 在本地仓库书写代码&#xff08;这里可以编辑一个文本文件做测试&#xff0c;如hello.txt&#xff09; 5&#xff09;执行&#xff1a;git add 要让git管理的文件&#xff08;git add hello.txt&#xff09;>执行完此操作将我…...

支持大模型训练的计算机系统

摘要&#xff1a; 训练数据决定了基础大模型可用的理论信息&#xff0c;模型架构和训练目标决定了可以提取多少信息&#xff0c;计算机系统决定了实际可实现的内容。在数据和模型大小方面&#xff0c;系统是扩展的关键瓶颈&#xff0c;这两者似乎都可以可靠地跟踪能力的改进。在…...

SAP ABAP-AVL-OO方法中的ALV的如何自己添加按钮及其响应

ABAP-AVL-OO方法中的ALV的如何自己添加按钮及其响应 SAP在做报表开发中&#xff0c;不同公司对报表的风格往往各异&#xff0c;为此经常在使用OO方法做ALV报表中需要去掉自带的工具栏而自行添加一些工具按钮&#xff0c;下面将简单介绍一下添加按钮及如何响应的实现方法&#…...

uniapp移动端悬浮按钮(吸附边缘)

Uniapp移动端悬浮按钮可以通过CSS实现吸附边缘的效果。具体实现步骤如下&#xff1a; html&#xff1a; <movable-area class"movable-area"><movable-view class"movable-view" :position"position" :x"x" :y"y"…...

【成功】Linux安装Mysql8并设置远程连接

今天在新搞来的阿里云的服务器里安装MySQL8&#xff0c;记录一下过程&#xff1a; 这是MySQL的官网和下载地址&#xff1a;MySQL :: Download MySQL Community Server (Archived Versions) 1. 先进入安装目录 cd /usr/local 2. 安装 wget https://downloads.mysql.com/arch…...

高效纯化树脂A-2313 CPR

在化工、制药等行业中&#xff0c;对colorful chemicals的纯化一直是挑战。本文将为您介绍一款具有卓越性能的强碱性阴离子交换树脂——Tulsion A-2313 CPR。通过分析其特性和应用&#xff0c;展示其在colorful chemicals纯化领域的优势。 一、Tulsion A-2313 CPR离子交换树脂的…...

uni-app实现安卓原生态调用身份证阅读器读卡库读身份证和社保卡、银行卡、IC卡等功能

DONSEE系列多功能读写器Android Uniapp API接口规范V1.0.0 本项目Uniapp调用了身份证读卡器的库文件&#xff1a;DonseeDeviceLib-debug.aar&#xff0c;该库放到nativeplugins\donsee-card\android&#xff0c;然后会自动加载。SDK会自动检查是否拥有USB设备权限&#xff0c;…...

【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绘制折线的时候带上圆角

场景&#xff1a; 使用antv-g6 自定义边的时候&#xff0c;绘制折线&#xff0c;此时都是直角&#xff0c;需要加圆角&#xff0c;没找到属性&#xff0c;自己绘制&#xff1a; 最后使用了A&#xff08;elliptical Arc&#xff09;弧形 A命令用于画弧形。 A rx ry x-axis-r…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...