【学会动态规划】买卖股票的最佳时机 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分…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
