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

【学会动态规划】买卖股票的最佳时机 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)

目录 动态规划怎么学&#xff1f; 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后&#xff1a; 动态规划怎么学&#xff1f; 学习一个算法没有捷径&#xff0c;更何况是学习动态规划&#xff0c; 跟我…...

请解释一下CSS中的rem和em单位有什么不同,分别如何使用?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ CSS中的rem和em单位的区别和使用⭐ em单位使用示例&#xff1a; ⭐ rem 单位使用示例&#xff1a; ⭐ 区别和适用场景⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何…...

docker 导入镜像 REPOSITORY和tag都是null怎么解决

当使用 docker import 命令导入镜像时&#xff0c;REPOSITORY 和 TAG 字段可能会为 null&#xff0c;因为 docker import 命令不会保留镜像的元数据&#xff0c;例如镜像名称和标签。这是因为 docker import 命令主要用于将本地文件系统中的文件或目录导入为 Docker 镜像&#…...

c语言操作符

目录 运算符 移位操作符 左移操作符 右移操作符 位操作符 按位与& 按位或| 按位异或^ 异或交换数字 计算二进制中1的个数 关系操作符 逻辑操作符 条件操作符 逗号表达式 下标引用、函数调用和结构成员 隐式类型转换 整形提升实例&#xff1a; 算术转换 操作…...

python爬虫5:requests库-案例3

python爬虫5&#xff1a;requests库-案例3 前言 ​ python实现网络爬虫非常简单&#xff0c;只需要掌握一定的基础知识和一定的库使用技巧即可。本系列目标旨在梳理相关知识点&#xff0c;方便以后复习。 申明 ​ 本系列所涉及的代码仅用于个人研究与讨论&#xff0c;并不会对网…...

uni-app:实现点击按钮,进行数据累加展示(解决数据过多,导致出错)

效果 代码 核心代码 一、标签显示 <!-- 加载更多 --> <view class"load_more" v-if"info.length > pageNum * pageSize" tap"loadMore">加载更多 </view> v-if"info.length > pageNum * pageSize"&#xf…...

群晖6.X便捷的安装cpolar内网穿透

群晖6.X便捷的安装cpolar内网穿透 文章目录 群晖6.X便捷的安装cpolar内网穿透前言1. 下载cpolar的群晖套件1.1 打开群晖套件中心1.2 选择“手动安装”1.3 选择下载cpolar套件位置 2. 打开cpolar的Web-UI界面3. 注册会员 前言 随着硬件设备和软件技术的发展&#xff0c;以及数据…...

ffmpeg 4.4版本对MP4文件进行AES-CTR加密,和流式加密

对于ffmpeg的AES-CTR加密有两种方式&#xff0c;一个是普通的整个视频做加密&#xff0c;另一个是对视频做切片处理&#xff0c;然后进行加密。 一、对于普通的加密方式 直接使用下面的命令就行 ffmpeg -i animal.mp4 -vcodec copy -acodec copy -encryption_scheme cenc-aes…...

软件测试基础篇——Docker

1、docker技术概述 docker描述&#xff1a;docker是一项虚拟化的容器技术&#xff08;类似于虚拟机&#xff09;&#xff0c;docker技术给使用者提供一个平台&#xff0c;在该平台上可以利用提供的容器&#xff0c;对每一个应用程序进行单独的封装隔离&#xff0c;每一个应用程…...

MySQL刷题遇到的盲点(五)窗口函数

窗口函数 语法&#xff1a; <窗口函数> over (partition by <用于分组的列名>order by <用于排序的列名>) partition by&#xff1a;用来对表分组&#xff08; partition 子句可以省略&#xff0c;省略就是不指定分组&#xff09; order by&#xff1a;是…...

【java】基础——多态

多态基本知识思维导图 多态的代码实现&#xff0c;注意父类对象引用指向子类对象引用&#xff08;向上转型&#xff09;的方法&#xff0c;父类就可以调用子类重写的方法和派生的方法&#xff0c;但不能调用子类特有的方法&#xff1a; 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&#xff0c;y坐标 方法二 photoshop 菜单栏 视图菜单->标尺菜单项&#xff08;ctrlR&#xff09; 宽度和高度边上都有标尺&#xff0c;默认的是厘米&#xff0c;右键单机宽度和高度边上…...

SpringCloud实用篇3----Docker

1.初识Docker 1.1 什么是Docker 微服务虽然具备各种各样的优势&#xff0c;但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中&#xff0c;依赖的组件非常多&#xff0c;不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署&#xff0c;环境不一定一致…...

使用阿里云服务器搭建Discuz论坛网站教程基于CentOS系统

阿里云百科分享使用阿里云服务器建站教程&#xff0c;本文是搭建Discuz论坛&#xff0c;Discuz!是一款通用的社区论坛软件系统&#xff0c;它采用PHP和MySQL组合的基础架构&#xff0c;为您提供高效的论坛解决方案。本文介绍如何在CentOS 7操作系统的ECS实例上搭建Discuz! X3.4…...

gitee(码云)如何生成并添加公钥配置用户信息

一&#xff0c;简介 在使用Gitee的时候&#xff0c;公钥是必须的&#xff0c;无论是克隆还是上传。本文主要介绍如何本地生成和添加公钥到服务器&#xff0c;然后配置自己的用户信息&#xff0c;方便日后拉取与上传代码。 二&#xff0c;步骤介绍 2.1 本地生成公钥 打开git ba…...

C++QT教程3——手册4.11.1自带教程(笔记)——创建一个QT快速应用

文章目录 创建一个QT快速应用创建项目创建主视图添加应用逻辑为视图添加动画素材文件 参考文章 创建一个QT快速应用 本教程使用内置的QML类型&#xff0c;介绍了Qt Quick的基本概念。有关可以选择的用户界面选项的更多信息&#xff0c;请参阅用户界面。 本教程描述了如何使用…...

用友时空KSOA SQL注入漏洞复现(HW0day)

0x01 产品简介 用友时空KSOA是建立在SOA理念指导下研发的新一代产品&#xff0c;是根据流通企业最前沿的I需求推出的统一的IT基础架构&#xff0c;它可以让流通企业各个时期建立的IT系统之间彼此轻松对话&#xff0c;帮助流通企业保护原有的IT投资&#xff0c;简化IT管理&#…...

java中编写代码:如何以sftp的形式把文件从服务器上面下载下来?(有账号和密码)

在Java中&#xff0c;你可以使用JSch库来实现通过SFTP协议下载文件。以下是一个简单的示例代码&#xff1a; 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) 考研难度&#xff08;☆☆☆☆☆&#xff09; 内容&#xff1a;23考情概况&#xff08;拟录取和复试分数人数统计&#xff09;、院校概况、23初试科目、23复试详情、参考书目、各科目考情分析、各专业考情分析。 正文2178字&#xff0c;预计阅读&#xff1a;6分…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...