动态规划 —— dp 问题-买卖股票的最佳时机III
1. 买卖股票的最佳时机III
题目链接:
123. 买卖股票的最佳时机 III - 力扣(LeetCode)
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

2. 题目解析


3. 算法原理
状态表示:以某一个位置为结尾或者以某一个位置为起点
dp[i]表示:第i天结束之后,此时的最大利润 :两种情况:
1. f[i][j]表示:第i天结束之后,完成了j次交易,处于买入状态,此时的最大利润
2. g[i][j]表示:第i天结束之后,完成了j次交易,处于卖出状态,此时的最大利润
2. 状态转移方程
在第i-1天处于买入状态,看买入状态能不能到自己,看卖出状态能不能到买入状态,另一个状态也是如此,一共4种状态
买入状态到 卖出状态到 买入状态 什么都不干 -prices[i](买股票) 卖出状态 +prices[i](交易次数+1) 什么都不干 1. f[i][j] = max(f[i-1][j] , g[i-1][j] - prices[i])
2. g[i][j] = max(g[i-1][j] , f[i-1][j-1] + prices[i]
3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行
因为是在第i-1天处于买入/卖出状态,所以当交易次数为0时,就相当于在第i天为-1,那么就会导致越界
所以我们可以修改一下第二个状态转移方程来判断一下,我们可以看到卖出状态到自己的情况是不会改变的,所以只用修改买入状态到卖出状态 :
1. g[i][j] = g[i-1][j](此状态一定不会越界)
2. if(j-1>=0) g[i][j] = max(g[i][j] , f[i-1][j-1] + prices[i]
在查找f[i-1][j-1] + prices[i]状态的时候先判断一下 下标是否合法(if(j-1>=0)),然后再求max
定义一个正无穷大/小的时候涉及到需要进行加减操作的时候,不要使用INT_MIN/MAX,因为如果INT_MIN减去一个数的话就会变成一个非常大的整数而导致溢出,所以我们最好用 +/- 0x3f3f3f3f 来表示最小值
本题初始化就是先将表里的所有值都初始化为-无穷大,再把f[0][0] = --prices[0],g[0][0] = 0
4. 填表顺序
本题的填表顺序是:从上往下填写每一行,每一行从左往右,两个表同时填
5. 返回值 :题目要求 + 状态表示
因为是要最大利润,所以买入状态不用考虑
本题的返回值是:g表里最后一行里面的最大值
4. 代码
动态规划的固定四步骤:1. 创建一个dp表
2. 在填表之前初始化
3. 填表(填表方法:状态转移方程)
4. 确定返回值
class Solution {
public:const int INF=0x3f3f3f3f;//将无穷大赋予给INFint maxProfit(vector<int>& prices) {int n = prices.size();//1. 创建dp表//3:交易次数的三列:0,1,2,再将所有的位置都变成负无穷大vector<vector<int>>f(n,vector<int>(3,-INF));auto g=f;//2. 在填表之前初始化f[0][0]=-prices[0];g[0][0]=0;//3. 填表(填表方法:状态转移方程)for(int i=1;i<n;i++){for(int j=0;j<3;j++)//j只有0,1,2三种状态{f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]=g[i-1][j];if(j>=1)g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]);}}//g表里最后一行里面的最大值int ret=0;for(int j=0;j<3;j++)ret=max(ret,g[n-1][j]);return ret;}
};
未完待续~
相关文章:
动态规划 —— dp 问题-买卖股票的最佳时机III
1. 买卖股票的最佳时机III 题目链接: 123. 买卖股票的最佳时机 III - 力扣(LeetCode)https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/ 2. 题目解析 3. 算法原理 状态表示:以某一个位置为结尾或者…...
“绽放艺术风采、激发强国力量” 海南省第十一届中小学生艺术展演活动圆满开展
2024年11月1日,由省教育厅主办、琼台师范学院承办的海南省第十一届中小学生艺术展演省级展演活动在海口正式拉开帷幕。来自全省各市县、省属学校等共计4000余名师生参加本届中小学生艺术展演现场展演活动。 本届展演活动以“绽放艺术风采、激发强国力量”为主题&…...
Linux之文件和目录类命令详解(2)
Linux之文件和目录类命令详解(2) 1、mv-移动文件或重命名2、find-查找文件和目录3、locate-快速查找文件4、du-显示目录或文件的磁盘使用情况5、df-显示文件系统的磁盘空间使用情况6、chmod-更改文件或目录的权限7、chown-更改文件或目录的拥有者8、tree…...
NVR管理平台EasyNVR多品牌NVR管理工具/设备摄像头开启ONVIF的方法
NVR小程序接入平台EasyNVR作为一款功能强大的安防视频监控平台,以其出色的兼容性和灵活性,在智慧校园、智慧工厂、智慧水利等多个场景中得到了广泛应用。本文将重点介绍如何为大华摄像头开启ONVIF协议,以便与EasyNVR进行无缝对接。 大华大部分…...
Pr 视频过渡:沉浸式视频
效果面板/视频过渡/沉浸式视频 Video Transitions/Immersive Video Adobe Premiere Pro 的视频过渡效果中,沉浸式视频 Immersive Video效果组主要用于 VR 视频剪辑之间的过渡。 自动 VR 属性 Auto VR Properties是所有 VR 视频过渡效果的通用选项。 默认勾选&#x…...
SwiftUI开发教程系列 - 第1章:简介与环境配置
1.1 SwiftUI简介 SwiftUI 是 Apple 于 2019 年推出的声明式用户界面框架,旨在简化 iOS、macOS、watchOS 和 tvOS 应用的 UI 开发。与 UIKit 的命令式编程方式不同,SwiftUI 提供了一种声明式语法,让开发者可以以更加直观、简洁的方式构建 UI。…...
gitlab ci/cd搭建及使用笔记
记录下使用gitlab的ci/cd的devops构建过程中,一些易忘点或者踩坑点: 官方文档中英文(建议英文) https://docs.gitlab.com/ee/ci/yaml/artifacts_reports.html https://gitlab.cn/docs/jh/ci/pipelines/schedules.html为什么创建了…...
Xcode 16 中 Swift Testing 的参数化(Parameterized)机制趣谈
概述 我们之前曾在 《用接地气的例子趣谈 WWDC 24 全新的 Swift Testing 入门》系列博文以及《WWDC24(Xcode 16)中全新的 Swift Testing 使用进阶》博文中较为系统地介绍了今年 WWDC 24 中全新的 Swift Testing 测试系统。 不过 Swift Testing 的本领远…...
Python自动化运维DevSecOps与安全自动化
Python自动化运维DevSecOps与安全自动化 目录 🛡️ DevSecOps概念与实践🔍 自动化安全扫描与漏洞修复🧰 基于Python的安全审计与合规性检查🐳 云平台与容器安全:基于Python的容器扫描工具⚠️ 自定义安全检测与漏洞修…...
2024下半年系统架构师考试【回忆版】
2024年11月10日,系统架构师考试如期举行,屡战屡败的参试倒是把北京的学校转了好几所。 本次考试时间 考试科目考试时间综合知识、案例分析8:30 - 12:30论文14:30 - 16:30 综合知识 1、1-1000以内包含5的数字个数 2、 案例分析 1、RESTful 对于前后…...
UE5.4 PCG 自定义PCG蓝图节点
ExecuteWithContext: PointLoopBody: 效果:点密度值与缩放成正比...
迁移学习相关基础
迁移学习 目标 将某个领域或任务上学习到的知识或模式应用到不同但相关的领域或问题中。 主要思想 从相关领域中迁移标注数据或者知识结构、完成或改进目标领域或任务的学习效果。 概述 Target data:和你的任务有直接关系的数据,但数据量少ÿ…...
华为云计算HCIE-Cloud Computing V3.0试验考试北京考场经验分享
北京试验考场 北京考场位置 1.试验考场地址 北京市海淀区北清路156号中关村环保科技示范园区M地块Q21楼 考试场选择北京,就是上面这个地址,在预约考试的时候会显示地址,另外在临近考试的时候也会给你发邮件,邮件内会提示你考试…...
数据分析——学习框架
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
量化交易系统开发-实时行情自动化交易-3.4.2.Okex行情交易数据
19年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 接下来聊聊基于Okex交易所API获取行情数…...
pytorch实现深度神经网络DNN与卷积神经网络CNN
DNN概述 深度神经网络DNN来自人脑神经元工作的原理,通过在计算机中逻辑抽象出多个节点,接收处理并向后传递信息,实现计算机的自我学习,类比结构见下图: 该方法通过预测输出与实际值的差异不断调整节点参数࿰…...
芯片测试-LDO测试
LDO测试 💢LDO的简介💢💢压降💢💢决定压降的主要因素💢 💢LDO的分类及原理💢💢PMOS LDO💢💢PMOS LDO工作过程💢💢PMOS LDO…...
期权懂|期权新手看过来:看跌期权该如何交易?
期权小懂每日分享期权知识,帮助期权新手及时有效地掌握即市趋势与新资讯! 期权新手看过来:看跌期权该如何交易? 一、可以直接购买看跌期权: (1)选择预期下跌的标的资产。 (2&#…...
《深入浅出HTTPS》读书笔记(8):密码学Hash算法的分类
密码学Hash算法有很多,比如MD5算法、SHA族类算法,MD5早已被证明是不安全的Hash算法了,目前使用最广泛的Hash算法是SHA族类算法。 1)MD5 MD5是一种比较常用的Hash算法,摘要值长度固定是128比特。 MD5算法目前被证明已…...
大语言模型安全,到底是什么的安全
什么是AI安全 自ChatGPT问世以来,市场上涌现出了众多大型语言模型和多样化的AI应用。这些应用和模型在为我们的生活带来便利的同时,也不可避免地面临着安全挑战。AI安全,即人工智能安全,涉及在人工智能系统的开发、部署和使用全过…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...
未授权访问事件频发,我们应当如何应对?
在当下,数据已成为企业和组织的核心资产,是推动业务发展、决策制定以及创新的关键驱动力。然而,未授权访问这一隐匿的安全威胁,正如同高悬的达摩克利斯之剑,时刻威胁着数据的安全,一旦触发,便可…...
java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟
众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了,延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp ,边缘服务器拉流推送到云服务器 …...
SpringSecurity+vue通用权限系统
SpringSecurityvue通用权限系统 采用主流的技术栈实现,Mysql数据库,SpringBoot2Mybatis Plus后端,redis缓存,安全框架 SpringSecurity ,Vue3.2Element Plus实现后台管理。基于JWT技术实现前后端分离。项目开发同时采 …...
鼠标的拖动效果
1、变量的设置 let isDragging false; let startX; let startY; let endX; let endY; let box null;isDragging : 表示是否推拽startX、startY:表示起始坐标,相对于元素endX、endY:表示结束坐标,相对于元素box&…...
【Linux】进程的基本概念
目录 概念描述进程-PCB如何查看进程通过系统目录进行查看通过ps指令进行查看 通过系统调用获取进程的PID和PPID(进程标⽰符)通过系统调用创建子进程通过一段代码来介绍fork为什么要有子进程?fork为什么给子进程返回0,给父进程返回子进程的PIDfork函数到底…...
MongoDB账号密码笔记
先连接数据库,新增用户密码 admin用户密码 use admin db.createUser({ user: "admin", pwd: "yourStrongPassword", roles: [ { role: "root", db: "admin" } ] })用户数据库用户密码 use myappdb db.createUser({ user: &…...

