★ FEATURED ARTICLE 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类型。
阅读完成 · 觉得有帮助？
