【学会动态规划】买卖股票的最佳时机 IV(18)
目录
动态规划怎么学?
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后:
动态规划怎么学?
学习一个算法没有捷径,更何况是学习动态规划,
跟我一起刷动态规划算法题,一起学会动态规划!
1. 题目解析
题目链接:188. 买卖股票的最佳时机 IV - 力扣(LeetCode)

这道题跟上一道题是一模一样啊,我的评价是,当一个 CV 工程师,
我马上 CV 出结果:
上一题的代码:

这一题的代码:

虽然话是这么说,我们还是再做一遍这道题:
2. 算法原理
1. 状态表示
dp[ i ] 表示到第 i 天的时候,所能获得的最大利润,
实际上,我们还是可以将他分成两种情况:
买入状态和可交易状态,而且我们需要记录完成了几次交易
f [ i ][ j ] 表示第 i 天结束之后,完成了 j 次交易,处于 “买入” 状态的最大利润,
g [ i ][ j ] 表示第 i 天结束之后,完成了 j 次交易,处于 “可交易” 状态的最大利润,
这里再次说明,买入状态指的是手里有股票,
而可交易状态表示的是手里没有股票。
2. 状态转移方程
我们先从 f [ i ][ j ] 开始分析,就两种情况,一种是昨天是买入,一种是昨天是可交易状态,
买入状态啥也不干就行,可交易状态只要在今天买入就能进入买入状态,所以:
f [ i ][ j ] = max( f [ i - 1 ][ j ],g [ i - 1 ][ j ] - p [ i ] )
然后是 g [ i ][ j ] ,也是同样的两种情况,
如果是买入状态就卖出,当天的 j 是比现在小1的,如果是可交易状态,就啥也不干就行,所以:
g [ i ][ j ] = max( g[ i - 1 ][ j ],f [ i - 1 ][ j - 1 ] + p [ i ] )
3. 初始化
为了防止越界,我们需要对他进行一些特殊的处理,
然后为了防止前面的值影响后面的值,我们需要把数组内容初始化成负无穷大
然后把 f [ 0 ][ 0 ] = -p[ 0 ],让 g [ 0 ][ 0 ] = 0 即可
4. 填表顺序
从上往下,从左往右,两个表一起填
5. 返回值
g 表最后一行的最大值
3. 代码编写
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));auto g = f;f[0][0] = -prices[0], g[0][0] = 0;for(int i = 1; i < n; i++) {for(int j = 0; j < k + 1; j++) {f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j > 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ans = 0;for(auto e : g[n - 1]) ans = max(ans, e);return ans;}
};
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
相关文章:
【学会动态规划】买卖股票的最佳时机 IV(18)
目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 动态规划怎么学? 学习一个算法没有捷径,更何况是学习动态规划, 跟我…...
请解释一下CSS中的rem和em单位有什么不同,分别如何使用?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ CSS中的rem和em单位的区别和使用⭐ em单位使用示例: ⭐ rem 单位使用示例: ⭐ 区别和适用场景⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何…...
docker 导入镜像 REPOSITORY和tag都是null怎么解决
当使用 docker import 命令导入镜像时,REPOSITORY 和 TAG 字段可能会为 null,因为 docker import 命令不会保留镜像的元数据,例如镜像名称和标签。这是因为 docker import 命令主要用于将本地文件系统中的文件或目录导入为 Docker 镜像&#…...
c语言操作符
目录 运算符 移位操作符 左移操作符 右移操作符 位操作符 按位与& 按位或| 按位异或^ 异或交换数字 计算二进制中1的个数 关系操作符 逻辑操作符 条件操作符 逗号表达式 下标引用、函数调用和结构成员 隐式类型转换 整形提升实例: 算术转换 操作…...
python爬虫5:requests库-案例3
python爬虫5:requests库-案例3 前言 python实现网络爬虫非常简单,只需要掌握一定的基础知识和一定的库使用技巧即可。本系列目标旨在梳理相关知识点,方便以后复习。 申明 本系列所涉及的代码仅用于个人研究与讨论,并不会对网…...
uni-app:实现点击按钮,进行数据累加展示(解决数据过多,导致出错)
效果 代码 核心代码 一、标签显示 <!-- 加载更多 --> <view class"load_more" v-if"info.length > pageNum * pageSize" tap"loadMore">加载更多 </view> v-if"info.length > pageNum * pageSize"…...
群晖6.X便捷的安装cpolar内网穿透
群晖6.X便捷的安装cpolar内网穿透 文章目录 群晖6.X便捷的安装cpolar内网穿透前言1. 下载cpolar的群晖套件1.1 打开群晖套件中心1.2 选择“手动安装”1.3 选择下载cpolar套件位置 2. 打开cpolar的Web-UI界面3. 注册会员 前言 随着硬件设备和软件技术的发展,以及数据…...
ffmpeg 4.4版本对MP4文件进行AES-CTR加密,和流式加密
对于ffmpeg的AES-CTR加密有两种方式,一个是普通的整个视频做加密,另一个是对视频做切片处理,然后进行加密。 一、对于普通的加密方式 直接使用下面的命令就行 ffmpeg -i animal.mp4 -vcodec copy -acodec copy -encryption_scheme cenc-aes…...
软件测试基础篇——Docker
1、docker技术概述 docker描述:docker是一项虚拟化的容器技术(类似于虚拟机),docker技术给使用者提供一个平台,在该平台上可以利用提供的容器,对每一个应用程序进行单独的封装隔离,每一个应用程…...
MySQL刷题遇到的盲点(五)窗口函数
窗口函数 语法: <窗口函数> over (partition by <用于分组的列名>order by <用于排序的列名>) partition by:用来对表分组( partition 子句可以省略,省略就是不指定分组) order by:是…...
【java】基础——多态
多态基本知识思维导图 多态的代码实现,注意父类对象引用指向子类对象引用(向上转型)的方法,父类就可以调用子类重写的方法和派生的方法,但不能调用子类特有的方法: class Animal {public void makeSound()…...
Go语言使用cron/v3实现定时任务
一、获取cron/v3包 go get github.com/robfig/cron/v3v3.0.0安装v3版本的cron包。 二、创建cron调度器 使用cron.New()创建一个新的Cron调度器: c : cron.New()三、添加定时任务 使用AddFunc方法添加定时任务,参数是cron表达式和任务函数: c.AddFunc("* * * * *&quo…...
photoshop PS 查看像素坐标、像素颜色、像素HSB颜色
方法一 photoshop 菜单栏 窗口菜单->信息菜单项(F8), 在信息窗口里会有当前的 x,y坐标 方法二 photoshop 菜单栏 视图菜单->标尺菜单项(ctrlR) 宽度和高度边上都有标尺,默认的是厘米,右键单机宽度和高度边上…...
SpringCloud实用篇3----Docker
1.初识Docker 1.1 什么是Docker 微服务虽然具备各种各样的优势,但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中,依赖的组件非常多,不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署,环境不一定一致…...
使用阿里云服务器搭建Discuz论坛网站教程基于CentOS系统
阿里云百科分享使用阿里云服务器建站教程,本文是搭建Discuz论坛,Discuz!是一款通用的社区论坛软件系统,它采用PHP和MySQL组合的基础架构,为您提供高效的论坛解决方案。本文介绍如何在CentOS 7操作系统的ECS实例上搭建Discuz! X3.4…...
gitee(码云)如何生成并添加公钥配置用户信息
一,简介 在使用Gitee的时候,公钥是必须的,无论是克隆还是上传。本文主要介绍如何本地生成和添加公钥到服务器,然后配置自己的用户信息,方便日后拉取与上传代码。 二,步骤介绍 2.1 本地生成公钥 打开git ba…...
C++QT教程3——手册4.11.1自带教程(笔记)——创建一个QT快速应用
文章目录 创建一个QT快速应用创建项目创建主视图添加应用逻辑为视图添加动画素材文件 参考文章 创建一个QT快速应用 本教程使用内置的QML类型,介绍了Qt Quick的基本概念。有关可以选择的用户界面选项的更多信息,请参阅用户界面。 本教程描述了如何使用…...
用友时空KSOA SQL注入漏洞复现(HW0day)
0x01 产品简介 用友时空KSOA是建立在SOA理念指导下研发的新一代产品,是根据流通企业最前沿的I需求推出的统一的IT基础架构,它可以让流通企业各个时期建立的IT系统之间彼此轻松对话,帮助流通企业保护原有的IT投资,简化IT管理&#…...
java中编写代码:如何以sftp的形式把文件从服务器上面下载下来?(有账号和密码)
在Java中,你可以使用JSch库来实现通过SFTP协议下载文件。以下是一个简单的示例代码: import com.jcraft.jsch.Channel; import com.jcraft.jsch.ChannelSftp; import com.jcraft.jsch.JSch; import com.jcraft.jsch.Session; public class SFTPDownloa…...
【24择校指南】南京大学计算机考研考情分析
南京大学(A) 考研难度(☆☆☆☆☆) 内容:23考情概况(拟录取和复试分数人数统计)、院校概况、23初试科目、23复试详情、参考书目、各科目考情分析、各专业考情分析。 正文2178字,预计阅读:6分…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
