动态规划解决股票买卖问题：状态机DP实战

1. 问题背景与核心挑战

LeetCode 123题"买卖股票的最佳时机III"是算法练习中的经典动态规划问题。题目要求在一个价格序列中，通过最多两次买卖操作获取最大利润。这与常规的单次交易问题（如LeetCode 121题）相比，复杂度呈指数级增长。

实际场景中，这个问题模拟了金融市场中的波段操作策略。比如某基金经理在季度初买入科技股，在年中高点卖出；随后观察到新能源板块的上涨趋势，再次进行建仓。这种分阶段操作需要精确把握买卖时机，而状态机DP正是建模这类多阶段决策过程的利器。

2. 状态机DP模型解析

2.1 状态定义与转移

我们需要定义5个核心状态：

• dp0：初始状态（未持有股票）
• dp1：第一次买入后状态
• dp2：第一次卖出后状态
• dp3：第二次买入后状态
• dp4：第二次卖出后状态

状态转移方程如下：

python复制dp1 = max(dp1, dp0 - prices[i])  # 第一次买入
dp2 = max(dp2, dp1 + prices[i])  # 第一次卖出
dp3 = max(dp3, dp2 - prices[i])  # 第二次买入
dp4 = max(dp4, dp3 + prices[i])  # 第二次卖出

关键点：每个状态都代表当前可能的最大资金量，转移时需要考虑前序状态的最优解。

2.2 空间优化技巧

原始DP需要O(n)空间存储每天的状态。通过观察可以发现，当前状态仅依赖前一天的状态，因此可以优化到O(1)空间：

python复制def maxProfit(prices):
    dp0 = 0
    dp1 = dp3 = -float('inf')
    dp2 = dp4 = 0
    for p in prices:
        dp1 = max(dp1, dp0 - p)
        dp2 = max(dp2, dp1 + p)
        dp3 = max(dp3, dp2 - p)
        dp4 = max(dp4, dp3 + p)
    return dp4

实测表明，该解法在LeetCode上运行时间可达到96ms（Python3），超越98%的提