经典动态规划问题:含手续费的股票买卖【从 O(n) 到 O(1) 的优化解析】
题目理解
我们要在给定的股票价格数组 prices 中进行买卖操作,并尽可能多次交易以获取最大利润。每次交易都需要支付一定的手续费 fee,因此我们必须考虑如何通过合适的交易策略最大化利润。
在本题中,每一天可以选择:
- 不进行任何操作。
- 买入股票。
- 卖出股票(前提是已经持有股票)。
题目链接:714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)
动态规划思路
我们可以使用动态规划(DP)来解决这个问题。在动态规划中,我们定义两种状态:
- 持有股票状态(持仓):
hold[i]表示第i天结束时持有股票时的最大利润。 - 不持有股票状态(空仓):
cash[i]表示第i天结束时不持有股票时的最大利润。
状态转移方程
-
持有股票的状态:
我们有两种可能:- 我们在第
i天之前已经持有股票,那么hold[i]就和hold[i-1]相同。 - 我们在第
i天买入股票,那么需要从cash[i-1](前一天不持有股票的最大利润)中减去prices[i](当天股票价格)。
因此,持有股票状态的转移方程为:
h o l d [ i ] = max ( h o l d [ i − 1 ] , c a s h [ i − 1 ] − p r i c e s [ i ] ) hold[i] = \max(hold[i-1], cash[i-1] - prices[i]) hold[i]=max(hold[i−1],cash[i−1]−prices[i])
- 我们在第
-
不持有股票的状态:
我们有两种可能:- 我们在第
i天之前已经卖出了股票,那么cash[i]就和cash[i-1]相同。 - 我们在第
i天卖出股票,此时需要加上prices[i]的收入并扣除手续费fee。
因此,不持有股票状态的转移方程为:
c a s h [ i ] = max ( c a s h [ i − 1 ] , h o l d [ i − 1 ] + p r i c e s [ i ] − f e e ) cash[i] = \max(cash[i-1], hold[i-1] + prices[i] - fee) cash[i]=max(cash[i−1],hold[i−1]+prices[i]−fee)
- 我们在第
初始状态
hold[0] = -prices[0]:第0天如果买入股票,我们的利润就是负的第0天的股票价格。cash[0] = 0:第0天如果不买股票,利润为0。
最终结果
我们最终需要的是在最后一天结束时,不持有股票时的最大利润,即 cash[n-1],其中 n 是 prices 的长度。
C++ 实现
#include <vector>
#include <algorithm>
using namespace std;int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<int> hold(n), cash(n);hold[0] = -prices[0]; // 第 0 天持有股票cash[0] = 0; // 第 0 天不持有股票for (int i = 1; i < n; ++i) {cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee); // 不持有股票hold[i] = max(hold[i-1], cash[i-1] - prices[i]); // 持有股票}return cash[n-1]; // 最后一天不持有股票的最大利润
}
优化思路
这个基本解法需要两个数组 hold 和 cash,分别存储持有和不持有股票时的利润值。这会占用 O(n) 的空间。而实际上,在计算第 i 天的状态时,只依赖于 i-1 天的状态,因此我们可以使用两个变量代替数组,优化空间复杂度到 O(1)。
优化后的实现
#include <vector>
#include <algorithm>
using namespace std;int maxProfit(vector<int>& prices, int fee) {int n = prices.size();int hold = -prices[0]; // 持有股票时的最大利润int cash = 0; // 不持有股票时的最大利润for (int i = 1; i < n; ++i) {cash = max(cash, hold + prices[i] - fee); // 更新不持有股票的最大利润hold = max(hold, cash - prices[i]); // 更新持有股票的最大利润}return cash; // 最后一天不持有股票的最大利润
}
解释及示例
示例 1
输入:prices = [1, 3, 2, 8, 4, 9], fee = 2
输出:8
过程:
- 第 0 天:买入股票,
hold = -1,cash = 0。 - 第 1 天:卖出股票,
cash = max(0, -1 + 3 - 2) = 0,保持持有状态,hold = -1。 - 第 2 天:保持持有状态,
cash = 0,hold = max(-1, 0 - 2) = -1。 - 第 3 天:卖出股票,
cash = max(0, -1 + 8 - 2) = 5,hold = max(-1, 5 - 8) = -1。 - 第 4 天:买入股票,
cash = 5,hold = max(-1, 5 - 4) = 1。 - 第 5 天:卖出股票,
cash = max(5, 1 + 9 - 2) = 8,hold = 1。
最终结果:cash = 8。
示例 2
输入:prices = [1, 3, 7, 5, 10, 3], fee = 3
输出:6
- 第 0 天:买入股票,持有股票的利润为
hold = -1,不持有股票的利润为cash = 0。 - 第 1 天:卖出股票后利润为
cash = max(0, -1 + 3 - 3) = 0,持有状态hold = max(-1, 0 - 3) = -1。 - 第 2 天:卖出股票后利润为
cash = max(0, -1 + 7 - 3) = 3,持有状态hold = max(-1, 3 - 7) = -1。 - 第 3 天:保持不持有状态
cash = max(3, -1 + 5 - 3) = 3,持有状态hold = max(-1, 3 - 5) = -1。 - 第 4 天:卖出股票后利润为
cash = max(3, -1 + 10 - 3) = 6,持有状态hold = max(-1, 6 - 10) = -1。 - 第 5 天:保持不持有状态
cash = max(6, -1 + 3 - 3) = 6。
最终利润为 6。
关键点总结
-
最优子结构:第
i天的状态只取决于第i-1天的状态。 -
状态转移方程:
- 持有状态:
hold[i] = max(hold[i-1], cash[i-1] - prices[i]) - 不持有状态:
cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee)
- 持有状态:
-
空间优化:我们只需要两个变量
hold和cash,可以将空间复杂度从O(n)优化到O(1)。
相关文章:
经典动态规划问题:含手续费的股票买卖【从 O(n) 到 O(1) 的优化解析】
题目理解 我们要在给定的股票价格数组 prices 中进行买卖操作,并尽可能多次交易以获取最大利润。每次交易都需要支付一定的手续费 fee,因此我们必须考虑如何通过合适的交易策略最大化利润。 在本题中,每一天可以选择: 不进行任…...
Python画笔案例-088 绘制 滚动的汉字
1、绘制 滚动的汉字 通过 python 的turtle 库绘制 滚动的汉字,如下图: 2、实现代码 绘制 滚动的汉字,以下为实现代码: """滚动的汉字.py """ import time from turtle import * from write_patch import *width,height...
Redis 5.0 安装配置(Windows)
Redis 5.0之后支持Redis Stream等功能 下载地址:Releases tporadowski/redis GitHub 点击运行redis-server.exe 此外:Redis 6.0及以后版本目前都没有Windows版...
金融行业:办公安全防护专属攻略
在中国金融市场快速迈向数字化转型的进程中,数据安全与隐私保护成为了不容忽视的关键议题。面对不断升级的网络威胁和日益严格的监管要求,构建一个既能支持创新又能提供坚实防护的信息安全体系变得尤为重要。亿格云不断深耕办公安全领域,为金…...
python如何基于numpy pandas完成复杂的数据分析操作?
数据分析是现代数据科学的重要组成部分,Python作为一种强大的编程语言,提供了许多库来简化数据分析过程。 其中,NumPy和Pandas是两个最常用的库。NumPy主要用于数值计算,而Pandas则提供了强大的数据结构和数据分析工具。 本文将深入探讨如何利用这两个库进行复杂的数据分…...
Linux中定时任务调度工具——crontab
1.简介 crontab是Unix和类Unix操作系统(如Linux)中用于定时任务调度的工具。其名称来源于“cron”这个守护进程,它负责周期性地执行任务,并且“tab”表示这个工具的配置文件。用户可以通过配置crontab文件来设定定时任务…...
思维+差分,CF 1884C - Medium Design
目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 1884C - Medium Design 二、解题报告 1、思路分析 考虑 最大值 和 最小值…...
简单介绍冯诺依曼体系
现代的计算机, 大多遵守冯诺依曼体系结构 CPU中央处理器:进行算术运算和逻辑判断。存储器:分为外存和内存,用于存储数据(使用二进制方式存储)。输入设备:用户给计算机发号施令。输出设备:计算机…...
kernel32.dll下载地址:如何安全地恢复系统文件
关于从网络上寻找kernel32.dll的下载地址,这通常不是一个安全的做法,而且可能涉及到多种风险。kernel32.dll是Windows操作系统的核心组件之一,负责内存管理、进程和线程管理以及其他关键系统功能。因为kernel32.dll是系统的基础文件ÿ…...
【高等数学】多元微分学 (一)
偏导数 偏导数定义 如果二元函数 f f f 在 x 0 , y 0 x_0,y_0 x0,y0 的某邻域有定义, 且下述极限存在 lim Δ x → 0 f ( x 0 Δ x , y 0 ) − f ( x 0 , y 0 ) Δ x \lim_{\Delta x\to 0} \frac{f(x_0\Delta x,y_0)-f(x_0,y_0)}{\Delta x} Δx→0limΔxf(x0Δ…...
Python爬取京东商品信息,详细讲解,手把手教学(附源码)
Python 爬虫爬取京东商品信息 下面我将逐一解释每一部分的代码 导入库 from selenium import webdriver from selenium.webdriver.edge.service import Service from selenium.webdriver.edge.options import Options import time import random import csv from selenium.c…...
大家有没有了解过TLKS-PLGS这款接地电阻在线监测装置?它在电力系统中能发挥什么作用呢?
接地电阻在线监测仪(输电铁塔接地电阻监测装置、变电站接地电阻监测装置、三极法接地网电阻监测装置)在电力系统中发挥着至关重要的作用,具体来说,有以下几个方面: 一、实时监测预警。该装置采用激励脉冲技术…...
Shell中的函数
目录 一、系统函数 (一)前言 (二)常用的函数 basename [string/pathname] [suffix] 二、自定义函数 (一)语法 (二)脚本例子 三、函数实际案例 过程中的报错: …...
通过IP地址或者主机名添加打印机20241023
文印室打印机连接方式20241023 Win键盘搜索打印机和扫描仪点击添加打印机或扫描仪,等候片刻点击“我需要的打印机不在列表中”添加打印机,选择使用IP地址或主机名添加打印机点击下一步,设备类型选择自动检测输入主机名:即打印机有…...
基于SpringBoot+Vue智慧养老关爱系统【提供源码+答辩PPT+参考文档+项目部署】
💥 这两年毕业设计和毕业答辩的要求和难度不断提升,传统的JavaWeb项目缺少创新和亮点,往往达不到毕业答辩的要求! ❗如何解决这类问题? 让我们能够顺利通过毕业,我也一直在不断思考、努力、精进。通过2024年…...
新手教学系列——利用短效代理快速搭建代理池
引言 在进行高并发数据抓取时,很多人都会遇到频繁IP被封的问题。要解决这个问题,代理池的搭建就成了关键。通过频繁更换代理IP,我们可以绕过网站的反爬机制,提升抓取效率。然而,很多初学者可能会觉得构建一个健壮的代理池颇为复杂,尤其是需要快速切换的短效代理池。在这…...
实体与DTO如何转换
下面是一些常用的转换库: Dozer 该项目目前不活跃,并且很可能在未来被弃用。 ModelMapper 一个智能对象映射库,可自动将对象相互映射。它采用基于约定的方法,同时提供简单、重构安全的应用程序接口(API)来…...
Docker 安装Postgres和PostGIS,并制作镜像
1. 查找postgres和postgis现有的镜像和版本号 镜像搜索网站:https://docker.aityp.com/ 测试使用的是postgres:15.4 和 postgis:15-3.4 2、镜像拉取 docker pull postgres:15.4docker pull postgis/postgis:15-3.4镜像下载完成,docker images 查看如…...
ES6:let和const命令解读以及变量的解构赋值
有时候,我们需要的不是答案,而是一双倾听的耳朵 文章目录 let和const命令变量的解构赋值 let和const命令 let和const命令都是声明变量的关键字,类同varlet特点 用来声明变量,不能再次定义,但是值可以改变存在块级作用…...
java-collection集合整理0.9.4
java-集合整理0.9.0 基本结构基本概念实例化举例遍历获取指定值 2024年10月17日09:43:16–0.9.0 2024年10月18日11:00:59—0.9.4 基本结构 Collection 是最顶级的接口。分为 List 和 Set 两大类。List 分为:ArrayList、LinkedList、Vector。Set 分为:Ha…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
