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

「动态规划」买卖股票的最佳时机

力扣原题链接,点击跳转。

给定一个整数数组prices,prices[i]表示股票在第i天的价格。你最多完成2笔交易。你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。设计一个算法计算最大利润。

我们用动态规划的思想来解决这个问题。首先确定状态表示。我们用f和g分别表示「买入」和「卖出」状态(处于「买入」状态时,手里有股票;处于「卖出」状态时,手里没有股票)。用i表示第i天结束时的状态。用j表示当前完成了j笔交易。也就是说,用f[i][j]表示在第i天结束时,处于「买入」状态下,完成了j笔交易,此时的最大利润;用g[i][j]表示在第i天结束时,处于「卖出」状态下,完成了j笔交易,此时的最大利润。

接下来推导状态转移方程。首先考虑f[i][j],如果第i-1天结束时处于「买入」状态,那么需要在第i天「持有股票」,就能在第i天结束时依然处于「买入」状态,由于「持有股票」并不会改变完成的交易次数,也不会改变利润,所以此时f[i][j]=f[i-1][j];如果第i-1天结束时处于「卖出」状态,那么需要在第i天「买入股票」,就能在第i天结束时处于「买入」状态,由于「买入股票」并不会改变完成的交易次数,但是会使利润减少第i天的股票价格,所以此时f[i][j]=g[i-1][j]-prices[i]。由于要求的是最大利润,所以f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i])。

接着考虑g[i][j],如果第i-1天结束时处于「买入」状态,那么需要在第i天「卖出股票」,就能在第i天结束时处于「卖出」状态,由于「卖出股票」后就完成了一次完整的交易,所以在第i-1天结束时的交易次数会比第i天结束时的交易次数少1,即第i-1天结束时的交易次数是j-1,同时「卖出股票」会使利润增多第i天的股票价格,所以此时g[i][j]=f[i-1][j-1]+prices[i];如果第i-1天结束时处于「卖出」状态,那么需要在第i天「观望」,就会在第i天结束时依然处于「卖出状态」,而「观望」并不会改变交易次数和利润,所以此时g[i][j]=g[i-1][j]。由于要求的是最大利润,所以g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j])。

接下来考虑初始化的问题。再次观察状态转移方程:f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]),g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j])。由于f[i][j]和g[i][j]都会依赖于i-1,所以初始化2个表的最上面一行。注意到j的取值范围是[0,2],故需要初始化的坐标有:(0,0)、(0,1)和(0,2)。不过,(0,1)和(0,2)说明在第0天结束时已经至少完成了1笔交易,也就是说,会在第0天「买入后立刻卖出股票」,这种操作是没有意义的,因为浪费了交易次数。所以,为了让(0,1)和(0,2)的值不影响取max的结果,应该把这两个位置初始化为-∞,即-0x3f3f3f3f,注意不是INT_MIN,防止计算g[i-1][j]-prices[i]时溢出。所以,现在只需要考虑f[0][0]和g[0][0]。其中f[0][0]表示在第0天结束时处于「买入」状态,只需要在第0天「买入股票」,即f[0][0]=-prices[0];g[0][0]表示在第0天结束时处于「卖出」状态,只需要在第0天「观望」,即g[0][0]=0。

还有另一个地方有可能越界。注意到g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j]),会依赖于j-1,所以理论上还需要初始化g表的最左边一列。但是这么做的话,会让f表和g表对应不上,导致细节问题更难处理。所以我们采取另一种方法。j代表的是交易次数,之所以j-1有可能越界,是因为这样算出来的交易次数是-1。既然不存在交易次数是-1的情况,我们只需要判断一下,如果j-1≥0,才计算g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j]),否则g[i][j]=g[i-1][j]即可。这样,就不存在越界的风险了。

填表时应从上往下填每一行,每一行从左往右填,且f表和g表同时填。最终应返回g表的最后一行的最大值,这是因为要想获取最大利润,就一定要在最后一天结束时处于「卖出」状态,且不确定此时的交易次数。我们来分析一下dp表的规模。由于没有加上虚拟节点,所以行数应与实际天数相同,即prices的元素个数n;由于j的所有可能取值是0、1和2,所以有3列。综上,f表和g表的大小均为n×3。

class Solution {
public:int maxProfit(vector<int>& prices) {const int INF = 0x3f3f3f3f;int n = prices.size();// 创建dp表vector<vector<int>> f(n, vector<int>(3, -INF));auto g = f;// 初始化f[0][0] = -prices[0];g[0][0] = 0;// 填表for (int i = 1; i < n; i++){for (int j = 0; j < 3; j++){f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);g[i][j] = g[i-1][j];if (j - 1 >= 0)g[i][j] = max(g[i][j], f[i-1][j-1] + prices[i]);}}// 求g表最后一行的最大值return *max_element(g[n-1].begin(), g[n-1].end());}
};

这道题还有个终极版本:力扣原题链接,点击跳转。

把限定的交易次数从2次改为k次,其余条件不变,求最大利润。

分析思路完全一样。状态表示和状态转移方程不变。初始化方式不变,依然是最上面一行除了f[0][0]=-prices[0]和g[0][0]=0之外都初始化为-∞。填表顺序不变。最后依然是返回g表最后一行的最大值。只有表的规模从n×3变为了n×(k+1)。

代码的话,只需要把上道题的代码的3修改为k+1即可。事实上,上道题就是本题中k=2时的特殊情况。除此之外,还有一个点值得优化,最多的交易次数一定不会超过总天数的一半,比如总天数是10天,那么最多交易5次;总天数是9天,那么最多交易4次。

class Solution {
public:int maxProfit(int k, vector<int>& prices) {const int INF = 0x3f3f3f3f;int n = prices.size();// 交易次数不会超过总天数的一半k = min(k, n/2);// 创建dp表vector<vector<int>> f(n, vector<int>(k+1, -INF));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 - 1 >= 0)g[i][j] = max(g[i][j], f[i-1][j-1] + prices[i]);}}// 求g表最后一行的最大值return *max_element(g[n-1].begin(), g[n-1].end());}
};

相关文章:

「动态规划」买卖股票的最佳时机

力扣原题链接&#xff0c;点击跳转。 给定一个整数数组prices&#xff0c;prices[i]表示股票在第i天的价格。你最多完成2笔交易。你不能同时参与多笔交易&#xff08;你必须在再次购买前出售掉之前的股票&#xff09;。设计一个算法计算最大利润。 我们用动态规划的思想来解决…...

Java 并发编程面试二

目录 一、并发编程三要素? 二、实现可见性的方法有哪些? 三、多线程的价值? 四、创建线程的有哪些方式? 五、创建线程的三种方式的对比? 六、Java 线程具有五中基本状态 七、什么是线程池?有哪几种创建方式 八、四种线程池的创建 九、线程池的优点? 十、常用的…...

成功解决“ModuleNotFoundError: No Module Named ‘utils’”错误的全面指南

成功解决“ModuleNotFoundError: No Module Named ‘utils’”错误的全面指南 在Python编程中&#xff0c;遇到ModuleNotFoundError: No Module Named utils这样的错误通常意味着Python解释器无法找到名为utils的模块。这可能是由于多种原因造成的&#xff0c;比如模块确实不存…...

Nvidia Jetson/Orin +FPGA+AI大算力边缘计算盒子:公路智能巡检解决方案

项目背景 中国公路网络庞大&#xff0c;总里程超过535万公里&#xff0c;高速公路里程位居世界前列。面对基础设施存量的不断增长&#xff0c;公路养护管理已迈入“建管养并重”的新时代。随着养护支出的逐年攀升&#xff0c;如何提升养护效率、降低管理成本&#xff0c;成为亟…...

【Maxcompute】geohash转经纬度,经纬度转geohash,计算geohash九宫格

1.梳理、总结经纬度处理在Maxcompute平台上的实战应用,如geohash转经纬度,经纬度转geohash,计算geohash九宫格等。 2.欢迎批评指正,跪谢一键三连! 文章目录 1.部署代码1.部署代码 部署至Maxcompute(ODPS)-DataWorks平台,去掉代码注释即可#coding:utf-8 # from odps.udf…...

【R语言基础】如何更新R版本

文章目录 概要流程细节具体步骤 概要 提示&#xff1a;由于软件包的更新&#xff0c;所以需要更新R至新版本 流程细节 查看当前R版本 R.version下载更新包&#xff1a;installr install.packages("installr")library(installr)跟着向导一步步执行安装 具体步骤 …...

Python知识点10---函数

提前说一点&#xff1a;如果你是专注于Python开发&#xff0c;那么本系列知识点只是带你入个门再详细的开发点就要去看其他资料了&#xff0c;而如果你和作者一样只是操作其他技术的Python API那就足够了。 Python的函数和Scala的函数很像&#xff0c;语法很简单&#xff0c;注…...

有哪些挣钱软件一天能赚几十元?盘点十个能长期做下去的挣钱软件

在这个信息爆炸的时代&#xff0c;每个人都在寻找快速赚钱的秘诀。很多人做兼职副业的目标并不是获得很大的成功&#xff0c;大部分人一天能赚几十就心满意足了。 今天&#xff0c;我要带你一探究竟&#xff0c;揭秘那些能让你日赚几十元的挣钱软件。准备好了吗&#xff1f;让我…...

CentOS7安装MySQL教程

第一章 检查是否安装了Mysql 1.1 yum检查 yum list installed | grep mysql 1.2 安装则直接删除 yum remove xxx 1.3 rpm检查 rpm -qa | grep -i mysql # 有则直接删除 rpm -e --nodeps xxx 第二章 正式安装MySQL 2.1 yum安装&#xff0c;下载mysql wget --no-check-ce…...

师彼长技以助己(3)逻辑思维

师彼长技以助己&#xff08;3&#xff09;逻辑思维 前言 上一篇文章进行了工程思维和产品思维的测试&#xff0c;并介绍了几个比较重要的产品思维模型。接下来本篇介绍工程思维。&#xff08;注意产品思维并不代表产品经理思维&#xff0c;工程思维也并不代表工程师思维&…...

LeetCode:反转链表I

文章收录于LeetCode专栏 LeetCode地址 反转链表I 题目 给你单链表的头节点head&#xff0c;请你反转链表&#xff0c;并返回反转后的链表。   示例 1&#xff1a; #mermaid-svg-IYmD16EKuu3CZWwV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size…...

oracle linux7安装oracle11g0204

1、平时需要修改 /etc/redhat-release文件为Red Hat Enterprise Linux 7,这次不需要了。 2、关闭selinx nano /etc/selinux/config 改为disabled 3、nano /etc/hosts 修改解析 在oracle服务器中增加 /etc/hosts中一个对应 192.168.1.10 CLOUD-MC-SQL1 4、修改系统文件 /…...

STM32--ADC

一、简介 *ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器 *ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁 *12位逐次逼近型ADC&#xff0c;1us转换时间 *输入电压范围&#xff1a;0~3.3V&…...

【TB作品】msp430f149单片机,读取ds18b20温度,显示到数码管,串口发送温度到电脑

功能 msp430f149单片机 读取ds18b20温度&#xff0c;显示到数码管&#xff0c;串口发送温度到电脑 部分程序 /************************************************* * 程序功能&#xff1a;用DS18B20测量室温并在数码管上显示。 * --------------------------------------…...

vue组合式和选项式

Vue中的组合式(Composition API)和选项式(Options API)是两种不同的编写组件逻辑的方法。 组合式API&#xff08;Composition API&#xff09;: 使用函数来定义组件逻辑&#xff0c;可以更灵活地重用和组合逻辑。使用setup函数作为组件的入口点&#xff0c;在这里可以访问pro…...

使用OpenCV创建全景图像

使用OpenCV创建全景图像 前言图像拼接策略创建全景图像相关链接前言 在本节中,我们将学习组合多个图像来创建全景图像。使用相机拍摄全景照片时,通常会拍摄多张照片,通过算法将这些图像中共同存在的元素(从左到右)映射到一张单独的图像中。为了执行图像的拼接,将利用 cv2 …...

Nios II 实现流水灯实验

Nios II 实现流水灯实验 一.硬件设计1.新建Quartus项目2. 设计Nios ii 二.软件设计 前言 实验目标&#xff1a; 学习 Quartus 、Platform Designer、Nios-II SBT 的基本操作&#xff1b;初步了解 SOPC 的开发流程&#xff0c;基本掌握 Nios-II 软核的定制方法&#xff1b;掌握 …...

Spring boot 随笔 1 DatasourceInitializer

0. 为啥感觉升级了 win11 之后&#xff0c;电脑像是刚买回来的&#xff0c;很快 这篇加餐完全是一个意外&#xff1a;时隔两年半&#xff0c;再看 Springboot-quartz-starter 集成实现的时候&#xff0c;不知道为啥我的h2 在应用启动的时候&#xff0c;不能自动创建quartz相关…...

vue3_组件间通信方式

目录 一、父子通信 1.父传子&#xff08; defineProps&#xff09; 2.父传子&#xff08;useAttrs&#xff09; 3.子传父&#xff08;ref&#xff0c;defineExpose &#xff09; 4.子传父&#xff08;defineEmits&#xff09; 5.子传父&#xff08;v-model&#xff09; …...

mysql的锁(全局锁)

文章目录 mysql按照锁的粒度分类全局锁概念&#xff1a;全局锁使用场景&#xff1a;全局锁备份案例&#xff1a; mysql按照锁的粒度分类 全局锁 概念&#xff1a; 全局锁就是对整个数据库实例加锁。MySQL 提供了一个加全局读锁的方法&#xff0c;命令是: Flush tables with…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

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

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

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...