动态规划解决股票买卖问题：最多两次交易的最大利润-北京尧图网络

1. 问题背景与核心挑战这道题目在LeetCode股票买卖系列中属于难度分水岭前两道题单次交易和无限次交易可以算是热身运动而本题则真正进入了动态规划的核心战场。题目要求在最多完成两笔交易的前提下计算股票买卖的最大利润。注意这里的两笔交易指的是完整的买卖组合。为什么说这是道标志性难题因为它首次引入了三维状态的概念。与常规的二维DP不同我们需要同时跟踪天数、交易次数和持仓状态这三个维度。我在第一次尝试时就被这个三维状态转移绕晕了直到画了状态机图才恍然大悟。关键理解每个交易日结束时你只能处于以下五种状态之一未进行任何操作第一次买入后持有股票第一次卖出后不持有股票第二次买入后持有股票第二次卖出后不持有股票实际编码时状态0可以省略因为利润始终为0。这才是真正需要处理的四个状态它们构成了我们DP数组的第二和第三维度。2. 三维DP的状态定义与转移方程2.1 DP数组的精确定义经过多次实践验证最清晰的DP定义应该是dp[i][k][h] # i: 第i天 (0 i n) # k: 已完成交易次数 (0 k 2) # h: 持仓状态 (0:不持有, 1:持有) # 值: 当前最大利润但在实际实现时可以进行空间优化。我发现将k和h合并为状态编码更直观dp[i][j] # i: 第i天 # j: 0-3分别对应上述四个有效状态2.2 状态转移的完整推导以五个状态为例转移方程如下状态1第一次买入可能来自前一天已买入或者当天新买入dp[i][1] max(dp[i-1][1], -prices[i])状态2第一次卖出可能来自前一天已卖出或者当天卖出从状态1转移dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i])状态3第二次买入可能来自前一天已买入或者用第一次的利润买入dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i])状态4第二次卖出可能来自前一天已卖出或者当天卖出从状态3转移dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i])易错点很多人在状态3的转移中忘记用第一次的利润(dp[i-1][2])减去当前股价而是直接使用-prices[i]这会导致第二次买入没有利用第一次的收益。3. 空间优化技巧与边界处理3.1 从三维降到一维的优化路径原始三维DP需要O(n32)的空间但通过观察可以发现第i天的状态只依赖于第i-1天交易次数k的变化是单向递增的因此可以优化到O(1)空间。我的实现方案是只用四个变量表示各个状态buy1 -prices[0] # 第一次买入后的余额 sell1 0 # 第一次卖出后的余额 buy2 -prices[0] # 第二次买入后的余额 sell2 0 # 第二次卖出后的余额每日更新逻辑for price in prices[1:]: buy1 max(buy1, -price) sell1 max(sell1, buy1 price) buy2 max(buy2, sell1 - price) sell2 max(sell2, buy2 price)3.2 边界条件的魔鬼细节初始资金设定第一次买入前资金为0所以buy1初始化为-prices[0]。但为什么buy2也初始化为-prices[0]因为允许在同一天完成买-卖-买操作。价格序列为空需要单独处理返回0。这是LeetCode常见陷阱。单日价格暴跌当某日价格远低于之前价格时要确保不会重复计算交易次数。我曾在测试用例[3,3,5,0,0,3,1,4]上栽过跟头。4. 完整代码实现与测试用例分析4.1 Python三维DP标准实现def maxProfit(prices): if not prices: return 0 n len(prices) dp [[[0]*2 for _ in range(3)] for __ in range(n)] # 初始化第一天各种状态 for k in range(3): dp[0][k][0] 0 # 不持有 dp[0][k][1] -prices[0] # 持有 for i in range(1, n): for k in range(1, 3): # 当前不持有前一天也不持有或前一天持有今天卖出 dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) # 当前持有前一天已持有或前一天不持有今天买入(消耗一次交易) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) return dp[-1][2][0]4.2 优化后的O(1)空间解法def maxProfit(prices): if not prices: return 0 buy1 buy2 -prices[0] sell1 sell2 0 for price in prices[1:]: buy1 max(buy1, -price) sell1 max(sell1, buy1 price) buy2 max(buy2, sell1 - price) sell2 max(sell2, buy2 price) return sell24.3 典型测试用例剖析基础案例[3,3,5,0,0,3,1,4] # 预期输出6 (5-3) (4-1)这个用例检验是否能捕捉非连续的两个上升波段。单调递减案例[7,6,4,3,1] # 预期输出0 (无法获利)验证算法在无利可图时的处理。极端波动案例[1,2,4,2,5,7,2,4,9,0] # 预期输出13 (7-1) (9-2)测试算法是否能跳过中间波动抓住主升浪。5. 从三维DP到通用K次交易解法5.1 问题泛化思路当我把本题解扩展到K次交易时发现状态转移存在统一模式for _ in range(k): buy max(buy, sell - price) sell max(sell, buy price)这引出了通用解法def maxProfit(k, prices): if not prices: return 0 if k len(prices)//2: # 退化为无限次交易 return sum(max(0, prices[i]-prices[i-1]) for i in range(1,len(prices))) buys [float(-inf)] * (k1) sells [0] * (k1) for price in prices: for i in range(1, k1): buys[i] max(buys[i], sells[i-1] - price) sells[i] max(sells[i], buys[i] price) return sells[k]5.2 不同解法的性能对比在LeetCode实测数据三维DP时间复杂度O(nk)空间复杂度O(nk*2)状态压缩时间复杂度O(n*k)空间复杂度O(k)贪心解法当kn/2时时间复杂度O(n)当k2时状态压缩版是最优选择。这也是面试中最常被要求实现的版本。6. 面试实战技巧与常见误区6.1 白板编码时的表达要点先明确说清楚状态定义我们需要同时跟踪天数、交易次数和持仓状态三个维度画出状态转移图即使不画在代码里也要口头描述主动讨论空间优化可能举例说明状态转移过程6.2 高频Follow-up问题如果手续费怎么处理 → 在每次卖出时减去fee如果交易有冷却期 → 需要增加状态表示冷却如何输出具体交易日期 → 需要记录路径6.3 我掉过的三个坑初始状态错误曾将buy2初始化为0忽略了可以在第一天完成首次买卖后立即二次买入。转移顺序错误必须先计算sell再计算buy否则会使用当天的buy值。正确的顺序应该是prev_buy1 buy1 buy1 max(buy1, -price) sell1 max(sell1, prev_buy1 price) # 使用前一天的buy1整数溢出当价格很大时Python没问题但在Java/C中要注意使用long类型。

动态规划解决股票买卖问题：最多两次交易的最大利润

相关推荐

金融数据建模的挑战与专业解决方案

impeccable怎么用？拆词根、辨近义、懂搭配，彻底告别高分词翻车

FANUC机器人线跟踪调试指南：编码器标定、框架同步与避坑

更多资讯

嵌入式Linux与安卓驱动开发实战：从内核模块到HAL层全链路解析

STM32C5嵌入式开发实战：从CubeMX配置到调试踩坑全记录

SiC MOSFET Boost PFC设计实战：从选型到EMI调试全解析

AGV/AMR导航控制器：从原理到调试的工程实践指南

Delphi源码下载精讲：实景聊天系统v3源码分析与改造

超微H12SSL-i主板USB卡顿排查与调优：从固件到供电的完整方案

今日更新

微信个人号API开发案例：图片/语音/视频消息怎么下载解析存到本地？

Python股票自动交易系统源码解析：从行情获取到风控的完整链路

视酷酷信IM源码部署指南：Java 17+MySQL 8.0.33实战配置

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？