动态规划状态机精解：买卖股票的最佳时机 III 问题

1. 项目概述理解“买卖股票的最佳时机 III”的核心挑战买卖股票的问题在算法面试和日常刷题中绝对是高频中的高频。它不像一些纯数学推导的题目而是完美地将现实世界的金融交易逻辑抽象成了一个动态规划模型考察的是你如何将复杂约束转化为清晰的状态定义和转移方程。今天要拆解的这道123. 买卖股票的最佳时机 III可以说是这个系列里承上启下的关键一题。它不再是简单的“只能买卖一次”121题或者“可以无限次买卖”122题而是加上了“最多可以完成两笔交易”这个核心限制。这意味着什么意味着你不能再像无限次买卖那样简单地贪心每一天的上涨也不能像单次买卖那样只维护一个历史最低价。你必须精确地记录在每一天结束时你处于第几次交易、持有或不持有股票的状态。这直接引入了“状态机”的思想。很多朋友卡在这里就是因为对“状态”的理解不够透彻或者被“最多两次”这个条件搞晕了不知道如何设计状态数组。我将带你从最朴素的想法开始一步步推导出最优的动态规划解法并给出可以直接“抄作业”的Python和C代码。无论你是正在准备面试还是想深入理解动态规划的状态设计这篇文章都会让你有收获。2. 核心思路拆解从暴力搜索到状态机DP2.1 问题重述与难点分析题目通常这样描述给定一个整数数组prices它的第i个元素prices[i]是一支给定股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。这意味着在任意一天结束时你最多只能持有一股股票。核心难点交易次数限制“最多两笔”是一个硬性上限这直接决定了我们状态定义的维度。状态复杂性每一天你可能有多种“身份”从未买过、第一次买入后持有、第一次卖出后空仓、第二次买入后持有、第二次卖出后空仓。我们需要一个清晰的方式描述这些身份。全局最优与局部决策今天的决策买、卖、持有、观望会影响未来所有天的可能性不能只看眼前利益。2.2 思路演进三维DP、二维DP与空间优化最直观的想法是设计一个三维动态规划数组dp[i][k][0 or 1]。i表示第i天0 i n。k表示剩余的交易次数注意这里“交易”指一次完整的“买入卖出”k最大为2。有些定义喜欢用“已经完成”的交易次数本质等价但状态转移的方向不同。我更喜欢“剩余次数”因为初始状态更清晰。0 or 1表示当前是否持有股票0表示不持有1表示持有。那么dp[i][k][0]的含义就是在第i天结束时最多还能进行k次交易且当前不持有股票所能获得的最大利润。 同理dp[i][k][1]表示在第i天结束时最多还能进行k次交易且当前持有股票所能获得的最大利润。我们最终要求的是dp[n-1][2][0]即最后一天最多还能进行2次交易实际上可能没用完且不持有股票的最大利润。持有股票的状态利润肯定低于不持有因为股票要卖出才是利润所以最终答案是不持有状态。状态转移方程dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i])解释今天不持有股票有两种可能昨天就不持有今天继续观望利润继承dp[i-1][k][0]。昨天持有今天卖出利润是昨天的持有利润dp[i-1][k][1]加上今天卖出的收入prices[i]。注意卖出操作不消耗剩余交易次数k因为交易次数是在买入时扣减的这是一个关键理解点也有定义在卖出时扣减只要自洽即可。dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k1][0] - prices[i])解释今天持有股票有两种可能昨天就持有今天继续持有利润继承dp[i-1][k][1]。昨天不持有今天买入利润是昨天在交易次数多一次即k1的状态下的不持有利润dp[i-1][k1][0]减去今天买入的成本prices[i]。注意因为今天买入后剩余交易次数从k1变成了k所以参考的是dp[i-1][k1][0]。初始状态基准情况dp[-1][...][0] 0天数从0开始但我们可以想象第-1天交易开始前不持有股票的利润是0。dp[-1][...][1] -infinity交易开始前不可能持有股票用负无穷表示不可达。dp[...][0][0] 0如果剩余交易次数为0不允许再买入那么不持有股票的最大利润就是0无法进行任何交易。dp[...][0][1] -infinity剩余交易次数为0时不允许持有股票用负无穷表示。这个三维DP思路非常清晰但空间复杂度是 O(n * 3 * 2)。由于k只有0,1,2三种可能我们可以将其展开降维成二维DP用五个变量来表示每一天的五个关键状态这也就是常说的“状态机”DP也是本题最优解的核心。3. 状态机DP详解与五状态法3.1 五个状态的定义既然k很小0,1,2我们可以直接枚举出所有有意义的状态组合。关键在于理解k代表剩余次数但结合是否持有我们可以定义出五个清晰的状态它们贯穿整个交易过程buy1: 进行过第一次买入操作后当前持有第一支股票的状态下的最大利润。对应三维DP中的dp[i][2][1]剩余2次交易持有股票但这是第一次买入后的持有。sell1: 进行过第一次卖出操作后当前不持有股票的状态下的最大利润。对应三维DP中的dp[i][1][0]剩余1次交易不持有股票。buy2: 进行过第二次买入操作后当前持有第二支股票的状态下的最大利润。对应三维DP中的dp[i][1][1]剩余1次交易持有股票。sell2: 进行过第二次卖出操作后当前不持有股票的状态下的最大利润。对应三维DP中的dp[i][0][0]剩余0次交易不持有股票。rest: 一个辅助状态表示从未进行过任何交易利润始终为0。在迭代中它隐含在初始化里。注意这里的状态定义是“进行过某次操作后”这是一个非常巧妙且实用的定义。它使得状态转移变得直观buy1只能从rest或buy1转移来sell1只能从buy1转移来buy2只能从sell1转移来sell2只能从buy2转移来。3.2 状态转移方程与解释我们用buy1[i],sell1[i],buy2[i],sell2[i]分别表示第i天结束时的对应状态的最大利润。初始化第0天i0:buy1[0] -prices[0]如果第一天就买入利润是负的股价。sell1[0] 0第一天不可能完成第一次卖出因为还没买入所以利润为0。另一种理解是在同一天买入并卖出利润为0但题目通常不允许。buy2[0] -prices[0]第一天就进行第二次买入这看起来不合理因为第一次交易还没完成。但实际上这个状态可以被理解为“在同一天内完成了第一次买卖利润0然后又进行了第二次买入”。在动态规划中我们需要允许这种“状态存在但利润极差”的情况它会在后续被更优的状态覆盖。初始化为-prices[0]是安全的。sell2[0] 0同理第一天不可能完成第二次卖出。状态转移对于 i 0:buy1[i] max(buy1[i-1], -prices[i])buy1[i-1]: 昨天就已经是第一次买入后的持有状态今天继续持有。-prices[i]: 今天才进行第一次买入。注意因为是第一次买入之前利润为0所以买入后的利润直接是-prices[i]。这个max操作保证了我们总是在更低的股价买入。sell1[i] max(sell1[i-1], buy1[i-1] prices[i])sell1[i-1]: 昨天就已经完成第一次卖出今天继续空仓。buy1[i-1] prices[i]: 昨天持有第一支股票今天卖出。利润是昨天的持有利润加上今天卖出的收入。buy2[i] max(buy2[i-1], sell1[i-1] - prices[i])buy2[i-1]: 昨天就已经是第二次买入后的持有状态今天继续持有。sell1[i-1] - prices[i]: 昨天完成了第一次卖出今天用所得利润进行第二次买入。sell2[i] max(sell2[i-1], buy2[i-1] prices[i])sell2[i-1]: 昨天就已经完成第二次卖出今天继续空仓。buy2[i-1] prices[i]: 昨天持有第二支股票今天卖出。最终答案max(sell1[n-1], sell2[n-1])。实际上由于sell2包含了完成两笔交易的可能其利润不会低于只完成一笔交易的sell1所以答案就是sell2[n-1]。3.3 空间优化滚动变量观察状态转移方程第i天的状态只依赖于第i-1天的状态。因此我们完全不需要维护整个数组只需要四个变量在每一天滚动更新即可。这是动态规划常见的空间优化技巧。定义四个变量buy1: 当前第一次买入后的最大利润。sell1: 当前第一次卖出后的最大利润。buy2: 当前第二次买入后的最大利润。sell2: 当前第二次卖出后的最大利润。初始化buy1 buy2 -prices[0]sell1 sell2 0遍历prices(从第1天开始即i1)for price in prices[1:]: buy1 max(buy1, -price) # 可以是今天才第一次买 sell1 max(sell1, buy1 price) # 可以是今天第一次卖 buy2 max(buy2, sell1 - price) # 可以是今天第二次买 sell2 max(sell2, buy2 price) # 可以是今天第二次卖注意更新顺序buy1和sell1要用到旧的值buy2要用到更新前的sell1sell2要用到更新前的buy2。上面的写法在Python中是安全的因为赋值语句是顺序执行的。但在一些其他语言或理解上更严谨的做法是使用临时变量保存旧值。4. 完整代码实现与逐行解析4.1 Python 代码实现from typing import List class Solution: def maxProfit(self, prices: List[int]) - int: 计算最多完成两笔交易的最大利润。 参数: prices (List[int]): 股票每日价格列表 返回: int: 最大利润 n len(prices) if n 2: return 0 # 无法完成任何交易 # 初始化四个状态变量 # buy1: 第一次买入后持有的最大利润负数表示成本 # sell1: 第一次卖出后不持有的最大利润 # buy2: 第二次买入后持有的最大利润 # sell2: 第二次卖出后不持有的最大利润即最终答案 buy1 buy2 -prices[0] # 第一天如果买入利润为负的股价 sell1 sell2 0 # 第一天无法卖出利润为0 # 从第二天开始遍历 for i in range(1, n): # 保存旧值用于本轮的顺序计算非必须但逻辑更清晰 # 在Python中由于下面计算是立即赋值的且buy1, sell1等是标量 # 直接使用当前值进行计算其依赖的是上一轮迭代后的值所以顺序写即可。 # 但为了与状态转移方程严格对应我们可以这样理解 # new_buy1 max(buy1, -prices[i]) # new_sell1 max(sell1, buy1 prices[i]) # 这里的buy1是旧的 # new_buy2 max(buy2, sell1 - prices[i]) # 这里的sell1是旧的 # new_sell2 max(sell2, buy2 prices[i]) # 这里的buy2是旧的 # 然后同时赋值: buy1, sell1, buy2, sell2 new_buy1, new_sell1, new_buy2, new_sell2 # 实际简洁写法依赖语言特性结果正确 buy1 max(buy1, -prices[i]) sell1 max(sell1, buy1 prices[i]) buy2 max(buy2, sell1 - prices[i]) sell2 max(sell2, buy2 prices[i]) # 更严谨的、避免顺序依赖的写法 # prev_buy1, prev_sell1, prev_buy2, prev_sell2 buy1, sell1, buy2, sell2 # buy1 max(prev_buy1, -prices[i]) # sell1 max(prev_sell1, prev_buy1 prices[i]) # buy2 max(prev_buy2, prev_sell1 - prices[i]) # sell2 max(prev_sell2, prev_buy2 prices[i]) # 最终最大利润是第二次卖出后的状态因为它包含了完成0,1,2次交易的所有可能最优解 return sell2代码解析:边界处理如果价格天数少于2无法完成买入并卖出直接返回0。初始化将buy1和buy2初始化为-prices[0]表示如果第一天就买入无论是第一次还是第二次当前的利润实际上是负的成本。sell1和sell2初始化为0。核心循环从第二天开始遍历。循环体内的四行代码严格对应了上一节推导出的四个状态转移方程。返回值返回sell2。为什么不是max(sell1, sell2)因为在状态转移中sell2的更新总是参考了sell1的结果通过buy2。如果只完成一次交易是最优的那么在迭代过程中sell2会通过max(sell2, buy2 price)中的buy2可能为负和sell2继承之前的sell1来保持最大值。可以证明sell2最终一定不小于sell1。所以直接返回sell2即可。4.2 C 代码实现#include vector #include algorithm using namespace std; class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); if (n 2) return 0; // 初始化四个状态 int buy1 -prices[0]; int sell1 0; int buy2 -prices[0]; int sell2 0; // 遍历价格数组 for (int i 1; i n; i) { // 使用临时变量保存前一天的状态确保更新顺序正确 int prev_buy1 buy1; int prev_sell1 sell1; int prev_buy2 buy2; int prev_sell2 sell2; // 根据状态转移方程更新 buy1 max(prev_buy1, -prices[i]); // 第一次买入 sell1 max(prev_sell1, prev_buy1 prices[i]); // 第一次卖出 buy2 max(prev_buy2, prev_sell1 - prices[i]); // 第二次买入 sell2 max(prev_sell2, prev_buy2 prices[i]); // 第二次卖出 // 也可以写成更紧凑但可能不易理解的形式依赖求值顺序在C中也是从左到右 // sell2 max(sell2, buy2 prices[i]); // buy2 max(buy2, sell1 - prices[i]); // sell1 max(sell1, buy1 prices[i]); // buy1 max(buy1, -prices[i]); // 注意这种紧凑写法中等号右边的变量值是上一轮的值因为赋值尚未发生。 // 但为了绝对清晰和避免混淆推荐使用临时变量的写法。 } return sell2; } };C代码要点头文件使用vector和algorithm分别用于容器和max函数。临时变量在C中我显式地使用了prev_*临时变量来保存前一天的状态。这是最安全、最清晰的做法完全避免了因更新顺序可能带来的歧义。虽然像Python那样顺序写也可能得到正确结果因为表达式求值在赋值之前但显式保存旧值是好习惯。返回值同样是返回sell2。5. 实战演练与案例分析理论说再多不如看几个具体的例子走一遍状态转移的过程感受一下算法是如何工作的。5.1 案例一标准波动市场prices [3,3,5,0,0,3,1,4]这个序列有涨有跌是检验算法的好例子。天数 (i)价格buy1sell1buy2sell2解释03-30-30初始化13max(-3, -3)-3max(0, -33)0max(-3, 0-3)-3max(0, -33)0价格未变状态维持25max(-3, -5)-3max(0, -35)2max(-3, 0-5)-3max(0, -35)2价格上涨sell1更新为2第0天买第2天卖30max(-3, -0)0max(2, -30)2max(-3, 2-0)2max(2, -30)2价格暴跌buy1更新为0今天买更便宜buy2更新为2用第一次利润2元0成本买入40max(0, -0)0max(2, 00)2max(2, 2-0)2max(2, 20)2价格仍为0状态不变53max(0, -3)0max(2, 03)3max(2, 2-3)2max(2, 23)5价格上涨sell1更新为3第3天买第5天卖sell2更新为5第3天第二次买第5天卖利润2(3-0)561max(0, -1)0max(3, 01)3max(2, 3-1)3max(5, 21)5价格下跌buy2更新为3用sell1的3元1元买入成本-2这里注意buy2 max(2, 3-1)2等等我们算一下prev_sell13, price1, 所以 prev_sell1 - price 2。而 prev_buy22所以 max(2,2)2。表格中我写错了应为2。sell2用prev_buy22计算max(5, 21)5。所以第6天buy10, sell13, buy22, sell2574max(0, -4)0max(3, 04)4max(2, 3-4)2max(5, 24)6最后一天sell1更新为4第6天买不对buy1是0表示第一次买入成本是0但那是第3/4天。实际上sell1 max(3, 04)4意味着可以在第3天0元买入第7天4元卖出利润4。sell2更新为6这是最终答案。它对应的操作是第一次交易第0天3元买第2天5元卖利润2第二次交易第3天0元买第7天4元卖利润4总利润6。最终结果sell2 6。对应的最优操作路径是(买3, 卖5)利润2(买0, 卖4)利润4。注意实际操作中买入卖出日期不能重叠但这里“第3天0元买”指的是 prices[3]0 的那天与第一次卖出 prices[2]5 不冲突。5.2 案例二单调上涨市场prices [1,2,3,4,5]在无限次交易中利润就是所有上涨之和4。但这里限制两次交易。天数价格buy1sell1buy2sell201-10-1012max(-1, -2)-1max(0, -12)1max(-1, 0-2)-1max(0, -12)123max(-1, -3)-1max(1, -13)2max(-1, 1-3)-1max(1, -13)234max(-1, -4)-1max(2, -14)3max(-1, 2-4)-1max(2, -14)345max(-1, -5)-1max(3, -15)4max(-1, 3-5)-1max(3, -15)4最终结果sell2 4。最优策略是只进行一次交易第0天1元买入第4天5元卖出利润4。因为市场单调上涨一次交易就能捕捉全部涨幅第二次交易没有增加利润的空间。算法正确地得到了这个结果。5.3 案例三单调下跌市场prices [5,4,3,2,1]天数价格buy1sell1buy2sell205-50-5014max(-5, -4)-4max(0, -54)0max(-5, 0-4)-4max(0, -54)023max(-4, -3)-3max(0, -43)0max(-4, 0-3)-3max(0, -43)032max(-3, -2)-2max(0, -32)0max(-3, 0-2)-2max(0, -32)041max(-2, -1)-1max(0, -21)0max(-2, 0-1)-1max(0, -21)0最终结果sell2 0。任何交易都会亏损所以最优策略是不交易利润为0。通过这些案例可以看到状态机是如何动态地追踪“在某个阶段进行到第几次交易、持有或不持有”的最佳利润的。6. 常见问题与深度思考6.1 为什么buy2要初始化为-prices[0]这是一个容易困惑的点。从实际意义上讲第一天不可能完成第一次交易后再进行第二次买入。但在动态规划中我们初始化的是“状态”的可能利润值。初始化为-prices[0]是一个“安全”的初始值它表示一种“理论上可能但实际很差”的情况假设在同一天第0天我们以prices[0]的价格完成了第一次买卖利润为0然后又以prices[0]的价格买入了第二次。这样初始的buy2利润就是-prices[0]。在后续的max比较中如果存在更优的第二次买入时机比如用第一次卖出后的正利润去买入这个很差的初始值会被覆盖掉。如果初始化为0或一个很大的正数可能会错误地影响max操作。6.2 状态转移的顺序可以调换吗在使用了临时变量保存旧值的前提下四个状态的更新顺序是可以调换的因为新状态都只依赖于旧状态彼此之间没有依赖。例如先更新sell2再更新buy2再更新sell1最后更新buy1只要计算时用的都是prev_*值结果就是正确的。但是在没有使用临时变量、直接进行顺序赋值的情况下如Python简洁写法顺序是至关重要的。必须按照buy1 - sell1 - buy2 - sell2的顺序。因为sell1的计算依赖于当前的buy1我们希望是旧的buy1。buy2的计算依赖于当前的sell1我们希望是旧的sell1。sell2的计算依赖于当前的buy2我们希望是旧的buy2。Python的简洁写法之所以正确正是因为赋值语句是顺序执行的。当计算sell1 max(sell1, buy1 price)时等号右边的buy1是上一轮迭代后的值即旧的buy1因为本轮对buy1的赋值已经完成。这是一种“隐式”地使用了旧值。为了代码清晰和跨语言一致性我强烈推荐使用临时变量的写法这样逻辑一目了然也不容易出错。6.3 如何扩展到“最多交易 k 次”这是本题的自然延伸LeetCode 188. 买卖股票的最佳时机 IV。思路完全一致只是状态变量从4个变成了2*k个buy1, sell1, buy2, sell2, ..., buyk, sellk。我们可以用两个长度为k1的数组buy和sell来表示其中buy[j]表示进行完第j次买入持有第 j 支股票后的最大利润sell[j]表示进行完第j次卖出后的最大利润。状态转移方程为for j in range(1, k1): buy[j] max(buy[j], sell[j-1] - price) sell[j] max(sell[j], buy[j] price)初始化时buy[1..k] -prices[0],sell[0..k] 0。最终答案是sell[k]。当k很大时比如k n/2问题退化为无限次交易可以用贪心解决以优化时间。6.4 如果包含交易手续费或冷冻期呢这是买卖股票问题的另外两个经典变种。含手续费LeetCode 714在每次卖出的时候从利润中减去手续费fee即可。状态转移方程修改为sell max(sell, buy price - fee)对于无限次交易或对应地修改sell1,sell2。含冷冻期LeetCode 309卖出后需要等待一天才能再次买入。这需要引入第三个状态cooldown冷冻期或者更简单地在买入的状态转移时不是从sell转移而是从两天前的sell即sell[i-2]转移。对于本题最多两次交易状态会变得复杂但原理相通buy2[i] max(buy2[i-1], sell1[i-2] - prices[i])。6.5 如何输出具体的交易日期动态规划通常只记录最大利润。要输出具体的买卖日期需要额外记录状态转移的路径。我们可以用另一个数组path在每次状态发生“转移”即max选择了后者时记录下当前的天数i和是哪个操作如“第一次买入”、“第一次卖出”等。最后从最终状态sell2倒推回去就能重构出最优的交易序列。这是一个经典的动态规划路径还原问题在面试中有时会被问到。7. 总结与个人心得买卖股票 III 这道题是理解动态规划中“状态机”思想的绝佳例题。它教会我们的不仅仅是解一道题而是一种建模方法将复杂的过程分解为几个离散的状态定义清楚每个状态的含义然后找出状态之间如何转移。我个人的几点实操心得“剩余次数” vs “已完成次数”我个人更喜欢“剩余次数”的定义因为初始状态剩余k次很清晰。但无论哪种定义只要状态转移方程自洽最终都能得出正确结果。关键是理解其本质。空间优化是最后一步不要一开始就追求最优的空间复杂度。先写出清晰易懂的三维或二维DP确保逻辑正确。然后再观察状态依赖进行空间优化滚动数组、变量。这样思路更清晰调试也更容易。画状态转移图在纸上画出几个状态buy1,sell1,buy2,sell2以及它们之间的转移关系观望、买入、卖出对于理解问题有奇效。这就像是一个小小的自动机。测试用例要全面不要只测递增或递减序列。要测试波峰波谷、平台期、以及边界情况如空数组、单元素数组。像[1,2,4,2,5,7,2,4,9,0]这种有多个波动的序列能很好地检验算法是否真的找到了全局最优的两笔交易。理解max操作的涵义动态规划中的max代表的是“到当前位置为止处于该状态下的最优解”。它可能继承自前一天的同状态不作为也可能由其他状态通过一次操作转移而来作为。这个“最优子结构”是动态规划可行的核心。最后代码的简洁性固然重要但清晰性和正确性永远是第一位的。在面试中即使你写不出空间优化到O(1)的版本只要能清晰地阐述三维DP的思路并写出正确的状态转移方程就已经能拿到大部分分数了。当然如果你能流畅地写出最终的五状态法并解释清楚绝对是加分项。希望这篇详细的拆解能帮助你彻底拿下这道题并将其背后的思想应用到更多动态规划问题中去。