企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南聚焦于 AlgoNote 仓库中 LeetCode **第 123 题「买卖股票的最佳时机 III」**的完整解题链路：如何在"最多完成两笔交易、且不能同时参与多笔交易"的约束下，用动态规划求出最大利润。读完本文你将掌握"按交易日 × 交易状态"二维 DP 的状态设计、五状态转移方程的推导过程、边界初始化与最终答案的选取逻辑，并理解它与第 121、122、188 题构成的股票买卖 DP 系列在状态维度上的递进关系。

一、题目背景与核心约束

本题对应的题解文档位于 best-time-to-buy-and-sell-stock-iii.md，标签为数组、动态规划，难度为困难。

给定一个数组prices代表一只股票，其中prices[i]代表这只股票第i天的价格。最多可完成两笔交易，且不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。要求计算所能获取的最大利润。

与仅允许一笔交易的 第 121 题 相比，本题的难点在于：

1. 交易次数有了上限：最多两笔，可以是零笔、一笔或两笔；
2. 交易之间存在先后约束：第二次买入必须发生在第一次卖出之后，即状态之间存在严格的顺序依赖；
3. 不能通过简单的前后缀拆分直接套用单次交易的贪心/递推：虽然"第一笔交易在某个分割点之前、第二笔在之后"的拆解法可行，但动态规划的状态机建模是更通用、更易推广到任意k笔交易的方案。

二、状态设计：五状态刻画"每天结束时的持仓情况"

"最多可完成两笔交易"意味着总共有三种情况：买卖一次、买卖两次、不买卖。具体到每一天结束，账户可能处于5 种状态：

定义状态dp[i][j]，表示第i天处于第j种情况（0 <= j <= 4）下所获取的最大利润。

这里需要特别强调一个容易混淆的点（原文档明确指出）：第j种情况并不代表这一天一定要发生买入或卖出操作，而是描述"这一天结束时账户所处的买入/卖出状态"。例如：前一天完成了第一次买入，第二天没有任何操作，那么第二天就沿用前一天的"第一次买入"状态。这正是 DP 状态机建模中"状态持续"的含义——dp[i][j]记录的始终是截止到第i天为止该状态下的最优利润。

这种"按天数（阶段）线性推进、每个阶段维护多个状态"的建模方式，正是仓库 线性 DP 章节 所定义的线性动态规划：阶段按时间顺序线性划分，每个阶段的状态取值只依赖前一阶段。而"定义状态 → 推导状态转移方程 → 确定初始条件与边界 → 求解最终结果"的四步法，也与 动态规划基础章节 中归纳的动态规划解题范式完全一致。

三、状态转移方程：每个状态如何由前一天推出

接下来确定状态转移公式。由于状态之间存在严格的先后顺序（买入必须在卖出之前，第二次买入必须在第一次卖出之后），每个非0状态都可以由两种来源推出，取较大者：

状态0（未进行任何买卖）

不进行任何交易，利润恒为0，直接继承昨天的状态：

• dp[i][0] = dp[i - 1][0]

状态1（第一次买入状态）

• 不做任何操作，沿用前一天"第一次买入"状态的最大利润：dp[i][1] = dp[i - 1][1]
• 当天发生第一次买入（用当前价prices[i]买入，现金减少）：dp[i][1] = dp[i - 1][0] - prices[i]

取两者较大值：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

状态2（第一次卖出状态）

• 不做任何操作，沿用前一天"第一次卖出"状态：dp[i][2] = dp[i - 1][2]
• 当天发生第一次卖出（以当前价卖出，现金增加）：dp[i][2] = dp[i - 1][1] + prices[i]

取两者较大值：dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])

状态3（第二次买入状态）

• 不做任何操作，沿用前一天"第二次买入"状态：dp[i][3] = dp[i - 1][3]
• 当天发生第二次买入（必须先处于"第一次已卖出"状态）：dp[i][3] = dp[i - 1][2] - prices[i]

取两者较大值：dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])

状态4（第二次卖出状态）

• 不做任何操作，沿用前一天"第二次卖出"状态：dp[i][4] = dp[i - 1][4]
• 当天发生第二次卖出：dp[i][4] = dp[i - 1][3] + prices[i]

取两者较大值：dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

观察这组方程可以提炼出一个通用规律：所有买入状态（1、3）的转移形如max(继承, 前一状态 - prices[i])，所有卖出状态（2、4）的转移形如max(继承, 前一状态 + prices[i])。买入用减（现金流出），卖出用加（现金流入），而"前一状态"恰好是顺序上紧邻它的那个状态（买入前必须先卖出，卖出前必须先买入）。这一规律正是后续第 188 题推广到k笔交易时的核心模式。

四、边界初始化：第一天的五种状态

下面确定初始化的边界值。以第0天（第一天）为起点：

• 状态0：第一天不做任何操作，dp[0][0] = 0；
• 状态1：第一天第一次买入，花掉prices[0]，利润为负：dp[0][1] = -prices[0]；
• 状态2：第一次卖出可视为当天买卖、价格没有变化，无盈利：dp[0][2] = 0；
• 状态3：第二次买入同样是dp[0][3] = -prices[0]；
• 状态4：第二次卖出同样视作无盈利：dp[0][4] = 0。

注意原文档代码中实际只显式初始化了dp[0][1]和dp[0][3]为-prices[0]，其余状态由于 Python 中dp数组整体初始化为0，已经天然满足上述边界（dp[0][0] = dp[0][2] = dp[0][4] = 0）。

为什么-prices[0]这种"亏损"初始化是必要的？因为状态1与3代表"已持有股票"的持仓状态，其利润表达式是"现金余额"视角——买入后现金减少。若初始化为0，后续dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])会在尚未买入时错误地允许"空仓却记持仓利润"，导致状态语义被破坏。

五、最终答案：为什么取dp[size - 1][4]

在递推结束后，最大利润一定落在无操作（状态 0）、第一次卖出（状态 2）、第二次卖出（状态 4）这三种"空仓且交易已了结"的状态中，且为其中最大值。

由于转移过程中始终维护的是最大值，而任何卖出的利润都大于等于0（当天买卖利润为 0，低买高卖利润为正），因此：

• dp[size - 1][2] >= 0，dp[size - 1][4] >= 0；
• 如果最优方案实际只需要一笔交易（甚至不交易），那么在转移时我们允许"同一天内完成两笔交易"，一笔交易的状态可以平滑转移到两笔交易状态：dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])中，dp[i-1][3]可以从dp[i-1][2]（第一次卖出）推导而来，而dp[i-1][2]本身已经包含了最优的单笔交易利润。

因此最终答案可以直接取dp[size - 1][4]，无需再对dp[size - 1][2]和dp[size - 1][4]做额外取最大值。size为股票天数（数组长度）。

六、完整可运行代码

原文档给出的标准解法如下（List[int]需要from typing import List支持，实际提交到力扣平台时注解已由平台预置）：

class Solution: def maxProfit(self, prices: List[int]) -> int: size = len(prices) if size == 0: return 0 dp = [[0 for _ in range(5)] for _ in range(size)] dp[0][1] = -prices[0] dp[0][3] = -prices[0] for i in range(1, size): dp[i][0] = dp[i - 1][0] dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]) dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]) dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]) return dp[size - 1][4]

代码与状态转移方程一一对应，dp表的行数等于天数，列数为 5（五种状态）。dp[0][0]、dp[0][2]、dp[0][4]依赖数组初始化的0值，因此代码中只显式设置了两个买入状态的负利润初始值。

七、复杂度分析

• 时间复杂度：$O(n)$，其中n是数组prices的元素个数。只需按天做一次线性遍历，每天执行常数次（5 次）状态转移。
• 空间复杂度：$O(n)$。使用了一个size × 5的二维数组dp保存全部状态。

空间优化（从源码结构可以推断的进阶写法）：观察转移方程可以发现，第i天的所有状态只依赖第i - 1天的状态，因此可以用 5 个滚动变量替代二维数组，将空间复杂度降至 $O(1)$：

class Solution: def maxProfit(self, prices: List[int]) -> int: size = len(prices) if size == 0: return 0 # 五个状态变量，对应五状态初始化 dp0, dp1, dp2, dp3, dp4 = 0, -prices[0], 0, -prices[0], 0 for i in range(1, size): new_dp1 = max(dp1, dp0 - prices[i]) new_dp2 = max(dp2, dp1 + prices[i]) new_dp3 = max(dp3, dp2 - prices[i]) new_dp4 = max(dp4, dp3 + prices[i]) # dp0 恒为 0，无需更新 dp1, dp2, dp3, dp4 = new_dp1, new_dp2, new_dp3, new_dp4 return dp4

注意：滚动变量更新时需要使用前一天的旧值参与计算，因此引入new_*临时变量后统一赋值，避免同一天内新值覆盖旧值导致的状态串扰（例如dp3需要用到旧的dp2，而dp2在同轮已被新值更新）。

八、算法脉络：从一笔交易到任意 k 笔交易的 DP 家族

本题不是孤立的，它在仓库的题解体系中处于"股票买卖 DP 系列"的承上启下位置：

• 0121. 买卖股票的最佳时机（简单）：只允许1 笔交易，用两个变量minprice/maxprofit一趟遍历即可求解，本质上是"单状态"递推；

• 0122. 买卖股票的最佳时机 II（中等）：不限交易次数，贪心累加所有正差价sum(max(0, prices[i] - prices[i-1]))，或者用"持有 / 空仓"两状态 DP 求解；

• [0123. 买卖股票的最佳时机 III]（本文，困难）：最多2 笔交易，引入5 状态二维 DP；

• 0188. 买卖股票的最佳时机 IV（困难）：最多k 笔交易，将 5 状态推广为2 * k + 1状态，偶数序号表示买入、奇数序号表示卖出，转移方程统一为：

  • 买入（j为奇数）：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])
  • 卖出（j为偶数）：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])

  初始时对j = 1, 3, ..., 2k - 1的奇数（买入）状态赋-prices[0]，最终答案为dp[size - 1][2 * k]。从源码结构看，第 188 题的题解文档中明确写到"这道题是 0123 的升级版，不过思路一样"，可见 123 题正是理解这一系列状态机建模的关键入口。

此外，该系列还有两个带附加条件的变体：加入冷冻期的 0309 最佳买卖股票时机含冷冻期 与加入手续费的 0714 最佳买卖股票时机含手续费。它们同样采用"买入/卖出"状态机建模，只是在转移方程中额外处理"冷却一天"或"卖出时扣除手续费"的约束。

仓库的完整题解索引可参见 docs/solutions/0100-0199/index.md，股票买卖系列的四道核心题目（0121、0122、0123、0188）均收录于其中；各道题的归档列表还可在 题解列表 与 分类列表 中按需查阅。

九、小结

回顾本题的完整求解链条：

1. 约束识别：最多两笔交易且不能同时持仓 → 决定用"交易次数 × 持仓状态"建模；
2. 状态定义：dp[i][j]表示第i天处于第j种状态（0 未买卖、1 首买、2 首卖、3 二买、4 二卖）的最大利润；
3. 转移方程：每个状态 =max(昨天同状态继承, 昨天前驱状态 ± prices[i])，买入减价、卖出加价；
4. 边界初始化：第一天买入状态初始化为-prices[0]，卖出状态初始化为0；
5. 最终答案：由于一笔交易可以无缝转移到两笔交易状态，直接返回dp[size - 1][4]即可。

掌握了这五步，你不仅能独立解决本题，还能顺势推导出任意k笔交易的第 188 题、以及带冷冻期/手续费的各种变体——这正是状态机式动态规划在股票买卖问题家族中的通用威力所在。

• 教程
• 文档
• 知识库