【LeetCode】188. 买卖股票的最佳时机 IV
188. 买卖股票的最佳时机 IV(困难)
思路
状态定义
一、首先确定要一天会有几种状态,不难想到有四种:
- a.当天买入了股票;
- b.当天卖出了股票;
- c.当天没有操作,但是之前是买入股票的状态;
- d.当天没有操作,但是之前是卖出股票的状态;
同时操作四种状态有些复杂,通过分析,我们可以优化成两种状态:「当天持有股票」和「当天不持有股票」。这两种状态分别对应为 a/c 和 b/d 。
二、接下来考虑如何表示这两种状态:
- 最常见的方法是使用 dp[0] 和 dp[1] 来表示,但是这种方式不仅不方便识别数组,而且还增加了 dp数组的一个维度,就本题而言,这种定义方式会得到一个三维数组,难以操作。
- 所以建议直接使用能明确表示含义的两个dp数组,比如用 buy 表示持有股票的状态, sell 表示不持有股票的状态。
三、最后确定dp数组的维度:
- 首先必须要有表示天数 i 的维度;
- 还需要有表示买卖次数 k 的维度 j;
四、综上,得到了两个二维的dp数组:
buy[i][j]
表示到第 i 天为止,恰好进行 j 笔交易,并且当前处于持有股票的状态,在这种情况下的最大利润;sell[i][j]
表示到第 i 天为止,恰好进行 j 笔交易,并且当前处于不持有股票的状态,在这种情况下的最大利润;
确定递推公式
在确定递推公式的时候,需要明确一个概念: k什么时候发生变化。这道题默认一买一卖才算是一次完整的交易,所以只有在卖股票的情况下,k才会发生变化。
确定完k的变化后,递推公式就很容易得到,每种状态都由两种情况组合得到:
buy[i][j]
- c.第 i-1 天就持有股票,那么当天收益不变,所得现金就是昨天持有股票的收益:
buy[i-1][j]
; - a.第 i 天买入股票,所得现金就是昨天不持有股票的收益扣去今天的股票价格:
sell[i-1][j] - prices[i]
; - 综合上述两种情况,最大收益就是
max(buy[i-1][j], sell[i-1][j] - prices[i])
。
- c.第 i-1 天就持有股票,那么当天收益不变,所得现金就是昨天持有股票的收益:
sell[i][j]
- d. 第 i-1 天就不持有股票,那么当天收益不变,所得现金就是昨天不持有股票的收益:
sell[i-1][j]
; - b. 第 i 天售出股票,那么所得现金就是昨天持有股票的收益加上今天的股票价格:
buy[i-1][j-1] + prices[i]
; - 综合上述两种情况,最大收益就是
max(sell[i-1][j], buy[i-1][j-1] + prices[i])
。
- d. 第 i-1 天就不持有股票,那么当天收益不变,所得现金就是昨天不持有股票的收益:
根据我们对 k 的变化的定义,体现在递推公式中就是在推导 sell[i][j]
的第二种情况时用到的 buy[i-1][j-1]
,因为在卖出股票的时候,就完成了一次交易,因此k的次数加一,所以上一个持有股票的状态就是 j-1 。
dp数组的初始化
-
将所有的
buy[0][0...k]
和sell[0][0...k]
都设置为边界; -
对于
buy[0][0...k]
,由于对应 i = 0 ,因此只有 prices[0] 唯一的股价,所以如果要持有股票,只能选择买入,因此对于 k = 0,buy[0][0] = - prices[0]
。由于只有一天,不可能完成一次完整的交易(即不可能售出),所以对于任意的 k >= 1 ,将所有的buy[0][1...k]
设置一个非常小的值(这里使用 INT_MIN / 2) ,表示不合法的状态。 -
同理,对于
sell[0][0...k]
,对应于 i=0 ,只有 prices[0] ,所以如果要不持有股票,只能不进行任何操作,所以对于 k=0,sell[0][0] = 0
,所以对于任意的 k >= 1 ,同样是不合法状态,将所有的buy[0][1...k]
设置一个非常小的值(这里使用 INT_MIN / 2) 。
最终的返回结果
在遍历完所有的 prices 后,手上不持有股票对应的最大力利润一定严格大于手上持有股票对应的最大利润,然而完成的交易数不是越多越好(比如数组 prices 单调递减,此时不进行任何交易才是最优解),因此最终答案是 sell[n-1][0...k]
的最大值,即 return *max_element(sell[n-1].begin(), sell[n-1].end());
。
易错点
一、k 的范围:
由于一次完整的交易需要两天,如果交易次数 k 大于 n/2 ,则必然有一天交易了两次,这是没有意义的,因此我们可以减小 k 的值,再进行动态规划,即 k = min(k, n/2);
。
二、buy 数组的维数:
第二个维度是 k+1 维,表示 k 的范围从 0~k 。如果数组单调递减,此时不进行任何交易是最优解, k=0;
三、j 的循环:
由于 sell[i][j]
的状态转移方程中包含 buy[i-1][j-1]
,如果 j=0 时,这是一个不合法状态,所以无需对 sell[i][j] 进行状态转移,让它保持值为 0 即可,所以在 j=0 时,只需要对 buy[i][0] 单独处理。
代码
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();if(n == 0) return 0;vector<vector<int>> buy(n, vector<int>(k+1));vector<vector<int>> sell(n, vector<int>(k+1));// k值的预处理k = min(k, n/2);// 预处理buy[0][0] = -prices[0];sell[0][0] = 0;for(int i=1; i<=k; ++i){// 不能设置为 INT_MINbuy[0][i] = sell[0][i] = INT_MIN / 2;}for(int i=1; i<n; ++i){buy[i][0] = max(buy[i-1][0], sell[i-1][0] - prices[i]);for(int j=1; j<=k; ++j){buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i]);sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i]);}}return *max_element(sell[n-1].begin(), sell[n-1].end());}
};
空间压缩
从上述代码不难发现,当前持有股票和当前不持有股票的最大收益都只和前一个状态有关,buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i]); sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i]);
,因此可以对两个数组进行空间压缩,只留下第二个维度。
代码如下:
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();if(n == 0) return 0;vector<int> buy(k+1);vector<int> sell(k+1);// k值的预处理k = min(k, n/2);// 预处理buy[0] = -prices[0];sell[0] = 0;for(int i=1; i<=k; ++i){// 不能设置为 INT_MINbuy[i] = sell[i] = INT_MIN / 2;}for(int i=1; i<n; ++i){buy[0] = max(buy[0], sell[0] - prices[i]);for(int j=1; j<=k; ++j){buy[j] = max(buy[j], sell[j] - prices[i]);sell[j] = max(sell[j], buy[j-1] + prices[i]);}}return *max_element(sell.begin(), sell.end());}
};
参考资料:188. 买卖股票的最佳时机 IV
相关文章:

【LeetCode】188. 买卖股票的最佳时机 IV
188. 买卖股票的最佳时机 IV(困难) 思路 状态定义 一、首先确定要一天会有几种状态,不难想到有四种: a.当天买入了股票;b.当天卖出了股票;c.当天没有操作,但是之前是买入股票的状态ÿ…...

android studio RadioButton单选按钮
1.定义 <!--单选按钮--> <TextViewandroid:layout_marginTop"10dp"android:layout_width"match_parent"android:layout_height"wrap_content"android:text"请选择你的性别:"> </TextView> <RadioGrou…...
AI大模型快速发展,我们该如何应对?
文章目录 提问问题范例Prompt 公式 如何准确提问 随着人工智能技术的不断发展,聊天型大语言模型工具如 ChatGPT 在解决各种实际问题时具有越来越广泛的应用。这一技术的快速发展,不仅带来了更高的工作效率和更高的精度,同时也改变了人类的工作…...

java多线程BlockingDeque的三种线程安全正确退出方法
本文介绍两种BlockingDeque在多线程任务处理时正确结束的方法 一般最开始简单的多线程处理任务过程 把总任务放入BlockingDeque创建多个线程,每个线程内逻辑时,判断BlockingDeque任务是否处理完,处理完退出,还有任务就BlockingDe…...

从STM32F407到AT32F407(一)
雅特力公司的MCU有着性能超群,价格优越的巨大优势,缺点是相关资料少一些,我们可以充分利用ST的现有资源来开发它。 我用雅特力的STM32F437开发板,使用原子 stm32f407的开发板自带程序,测试串口程序,原设定…...

【数据结构】顺序表和链表基本实现(含全代码)
文章目录 一、什么是线性表1. 什么是顺序表动态开辟空间和数组的问题解释LeetCode-exercise 2. 什么是链表2.1链表的分类2.2常用的链表结构及区别2.3无头单向非循环链表的实现2.4带头双向循环链表的实现2.5循序表和链表的区别LeetCode-exercise 3. 快慢指针LeetCode-exercise 一…...

CMake : Linux 搭建开发 - g++、gdb
目录 1、环境搭建 1.1 编译器 GCC,调试器 GDB 1.2 CMake 2、G 编译 2.1 编译过程 编译预处理 *.i 编译 *.s 汇编 *.o 链接 bin 2.2 G 参数 -g -O[n] -l、-L -I -Wall、-w -o -D -fpic 3、GDB 调试器 3.1 调试命令参数 4、CMake 4.1 含义 4.2…...

大数据实战 --- 美团外卖平台数据分析
目录 开发环境 数据描述 功能需求 数据准备 数据分析 RDD操作 Spark SQL操作 创建Hbase数据表 创建外部表 统计查询 开发环境 HadoopHiveSparkHBase 启动Hadoop:start-all.sh 启动zookeeper:zkServer.sh start 启动Hive: nohup …...

三大本土化战略支点,大陆集团扩大中国市场生态合作「朋友圈」
“在中国,大陆集团已经走过30余年的发展与耕耘历程,并在过去10年间投资了超过30亿欧元。中国市场也成为了我们重要的‘增长引擎’与‘定海神针’。未来,我们将继续深耕中国这个技术导向的市场。”4月19日上海车展上,大陆集团首席执…...

为什么停更ROS2机器人课程-2023-
机器人工匠阿杰肺腑之言: 我放弃了ROS2课程 真正的危机不是同行竞争,比如教育从业者相互竞争不会催生ChatGPT…… 技术变革的突破式发展通常是新势力带来的而非传统行业的升级改革。 2013年也就是10年前在当时主流视频网站开启分享: 比如 …...

【SpringCloud常见面试题】
SpringCloud常见面试题 1.微服务篇1.1.SpringCloud常见组件有哪些?1.2.Nacos的服务注册表结构是怎样的?1.3.Nacos如何支撑阿里内部数十万服务注册压力?1.4.Nacos如何避免并发读写冲突问题?1.5.Nacos与Eureka的区别有哪些ÿ…...

ChatGPT+智能家居在AWE引热议 OpenCPU成家电产业智能化降本提速引擎
作为家电行业的风向标和全球三大消费电子展之一,4月27日-30日,以“智科技、创未来”为主题的AWE 2023在上海新国际博览中心举行,本届展会展现了科技、场景等创新成果,为我们揭示家电与消费电子的发展方向。今年展馆规模扩大至14个…...

拷贝构造函数和运算符重载
文章目录 拷贝构造函数特点分析拷贝构造函数情景 赋值运算符重载运算符重载operator<运算符重载 赋值运算符前置和后置重载 拷贝构造函数 在创建对象的时候,是不是存在一种函数,使得能创建一个于已经存在的对象一模一样的新对象,那么接下…...

本周热门chatGPT之AutoGPT-AgentGPT,可以实现完全自主实现任务,附部署使用教程
AutoGPT 是一个实验性的开源应用程序,它由GPT-4驱动,但有别于ChatGPT的是, 这与ChatGPT的底层语言模型一致。 AutoGPT 的定位是将LLM的"思想"串联起来,自主地实现你设定的任何目标。 简单的说,你只用提出…...
Mysql 优化LEFT JOIN语句
1.首先说一下个人对LEFT JOIN 语句的看法,原先我是没注意到LEFT JOIN 会影响到性能的,因为我平时在项目开发中,是比较经常见到很多个关联表的语句的。 2.阿里巴巴手册说过,连接表的语句最好不超过3次,但是我碰到的项目…...
全栈成长-python学习笔记之数据类型
python数据类型 数字类型 类型类型转换整型 intint() 字符串类型转换 浮点型保留整数 int(3.14)3 int(3.94)3浮点型 floatfloat() #####字符串类型 类型类型转换字符串 strstr() 将其他数据类型转为字符串 布尔类型与空类型 布尔类型 类型类型转换布尔型 boolbool()将其他…...
面试|兴盛优选数据分析岗
1.离职原因、离职时间点 2.上一份工作所在的部门、小组、小组人员数、小组内的分工 3.个人负责的目标,具体是哪方面的成本 4.为了降低专员成本,做了哪些方面的工作 偏向于机制、分析方法、思维,当下主要是对于部分高收入专员收入不合理的情况…...
Redis(08)主从复制master-slave replication
文章目录 redis主从复制一. 配置文件的方式设置1. 主节点配置:2. 从节点1配置:3. 从节点2配置: 二. 命令的方式设置1. 创建服务2. 设置主从节点3. 测试 三. 从节点升级为主节点四. 查看主从关系 redis主从复制 Redis主从复制是将一个Redis实例的数据复制到多个Redis实例&#…...

被chatGPT割了一块钱韭菜
大家好,才是真的好。 chatGPT热度一直上升,让我萌生了一个胆大而创新的想法, 把chatGPT嵌入到Notes客户机中来玩。 考虑到我已经下载了一个chatGPT的Notes应用(请见《ChatGPT APIs for HCL DOMINO》),想着…...

vue3+ts+pinia+vite一次性全搞懂
vue3tspiniavite项目 一:新建一个vue3ts的项目二:安装一些依赖三:pinia介绍、安装、使用介绍pinia页面使用pinia修改pinia中的值 四:typescript的使用类型初识枚举 一:新建一个vue3ts的项目 前提是所处vue环境为vue3&…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...

AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》
近日,嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》,海云安高敏捷信创白盒(SCAP)成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天,网络安全已成为企业生存与发展的核心基石,为了解…...
Oracle实用参考(13)——Oracle for Linux物理DG环境搭建(2)
13.2. Oracle for Linux物理DG环境搭建 Oracle 数据库的DataGuard技术方案,业界也称为DG,其在数据库高可用、容灾及负载分离等方面,都有着非常广泛的应用,对此,前面相关章节已做过较为详尽的讲解,此处不再赘述。 需要说明的是, DG方案又分为物理DG和逻辑DG,两者的搭建…...

华为OD机考- 简单的自动曝光/平均像素
import java.util.Arrays; import java.util.Scanner;public class DemoTest4 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint[] arr Array…...

无头浏览器技术:Python爬虫如何精准模拟搜索点击
1. 无头浏览器技术概述 1.1 什么是无头浏览器? 无头浏览器是一种没有图形用户界面(GUI)的浏览器,它通过程序控制浏览器内核(如Chromium、Firefox)执行页面加载、JavaScript渲染、表单提交等操作。由于不渲…...