买卖股票系列：状态机动态规划通用解法

1. 课程综述与核心逻辑初探

在算法面试的动态规划（DP）版块中，“买卖股票系列问题”被公认为考察开发者逻辑建模能力的标杆题目。这不仅是因为其高频的面试出镜率，更在于它是一个极佳的思维训练载体：从简单的贪心策略到复杂的约束处理，该系列问题完美展示了算法如何处理受限的最优决策。

本报告的核心使命是建立一套状态机 DP 的“通用解法（General Solution）”。在面对无限次交易（LC122）、冷冻期（LC309）以及 k 次交易限制（LC188）时，传统的贪心算法往往捉襟见肘——贪心仅在无约束条件下（如 LC122）生效，因为它能捕获所有的正向波段。然而，一旦引入交易次数限制或冷冻期，我们就必须具备“全局观”，为了未来的更大利润而放弃当下的局部收益。

状态机思想的优越性在于，它将全局优化问题转化为局部的状态转移问题。通过将每一天视为状态机中的一个节点，我们消除了对“过去任意天”的无效回溯，仅需关注当前状态与决策流转。这种思维模型是破解所有高阶 DP 题目的核心钥匙。

2. 核心题目描述与复杂度瓶颈

买卖股票系列问题的逻辑骨架高度统一，但细节处的约束直接决定了算法的复杂度上限。

2.1 通用框架规则

• 输入与输出： 输入一个整数数组 prices，其中 prices[i] 为第 i 天价格。目标是计算在遵循规则前提下的最大利润。
• 核心交易规则：
  • 持仓限制： 同一时间最多只能持有一股股票。
  • 交易原子性： 必须在再次购买前卖出手中持有的股票。
  • 变体约束： 包含交易次数上限 k、卖出后的“冷冻期”天数、或每笔交易的固定“手续费”。

2.2 复杂度瓶颈分析 (Complexity Bottlenecks)

• 时间复杂度： 数组长度通常达到 10^5，这意味着 O(n^2) 的回溯会超时，算法必须优化至 O(n) 或 O(nk)。
• 空间复杂度： 在处理大规模数据时，虽然 O(nk) 的 DP 表可以解决问题，但高级实现通常要求利用滚动数组技巧优化至 O(k) 或 O(1)。

3. 核心解题思路：从递归到状态机标准型

动态规划的本质是带有记忆化的搜索。我们需要站在第 i 天结束时的视角，分析当前所处的“处境”。

3.1 状态定义与“So What?”视角

我们将每一天的状态建模为两个核心维度：

1. 持有 (Hold): 第 i 天结束时，手中持有一股股票（可能是今天买的，也可能是之前买的）。
2. 未持有 (Unhold): 第 i 天结束时，手中空仓（可能是今天卖了，也可能是之前就没买）。

3.2 决策路径与状态转移

在状态机模型中，每一天的决策（买入、卖出、观望）驱动状态的流转。我们将 k 定义为剩余可交易次数，并在买入时扣除次数（代表一笔交易的开始）。

状态转移图可视化：

[ 未持有, k ] -- 买入 ( -prices[i], k-1 ) --> [ 持有, k-1 ]
[ 持有, k ]   -- 卖出 ( +prices[i] )      --> [ 未持有, k ]
[ 未持有 ]    -- 观望 ( 利润不变 )         --> [ 未持有 ]
[ 持有 ]      -- 观望 ( 利润不变 )         --> [ 持有 ]

3.3 状态转移方程

定义 dfs(i, j, k) 为前 i 天在状态 j、剩余交易次数为 k 时的最大利润：

• 未持有：dfs(i, 0, k) = max(dfs(i-1, 0, k), dfs(i-1, 1, k) + prices[i])
  • 逻辑： 昨天就没持有且今天观望，或者昨天持有且今天卖出。
• 持有：dfs(i, 1, k) = max(dfs(i-1, 1, k), dfs(i-1, 0, k-1) - prices[i])
  • 逻辑： 昨天就持有且今天观望，或者昨天没持有且今天新买入（消耗一次 k）。

冷冻期特例： 若存在 1 天冷冻期，买入决策需参考 dfs(i-2, 0, k-1)，即强制跳过前一天的卖出可能。

4. 多语言代码实现与关键细节

为了体现生产级别的代码素质，我们将重点展示如何处理边界位移（DP Table Offset）与状态初始化。

4.1 Python 实现：从递归到迭代 (以至多 k 次交易为例)

import math

# 1. 记忆化搜索版本 (直观逻辑)
def max_profit_dfs(k, prices):
    n = len(prices)
    # 使用数组而非字典以提升 N=10^5 时的性能
    memo = [[[-1] * (k + 1) for _ in range(2)] for _ in range(n)]

    def dfs(i, j, k):
        if k < 0: return -math.inf
        if i < 0:
            # 边界：i=-1时，若持有(j=1)是不可能的，返回负无穷；若未持有(j=0)利润为0
            return -math.inf if j == 1 else 0
        if memo[i][j][k] != -1: return memo[i][j][k]
        
        if j == 0: # 当前不持有
            res = max(dfs(i - 1, 0, k), dfs(i - 1, 1, k) + prices[i])
        else: # 当前持有
            res = max(dfs(i - 1, 1, k), dfs(i - 1, 0, k - 1) - prices[i])
        memo[i][j][k] = res
        return res

    return dfs(n - 1, 0, k)

# 2. 递推 (DP 表) 版本：使用 i+1 偏移量处理 i=-1
def max_profit_dp(k, prices):
    n = len(prices)
    # dp[i+1][j][k]
    dp = [[[-math.inf] * (k + 1) for _ in range(2)] for _ in range(n + 1)]
    
    # 初始化边界 i = -1 (对应 dp[0])
    for cur_k in range(k + 1):
        dp[0][0][cur_k] = 0
        
    for i, p in enumerate(prices):
        for cur_k in range(k + 1):
            # 不持有状态转移
            dp[i+1][0][cur_k] = max(dp[i][0][cur_k], dp[i][1][cur_k] + p)
            # 持有状态转移 (需判断 cur_k > 0)
            if cur_k > 0:
                dp[i+1][1][cur_k-1] = max(dp[i][1][cur_k-1], dp[i][0][cur_k] - p)
                
    return int(max(dp[n][0]))

4.2 性能与复杂度对比

维度	记忆化搜索	递推 (DP 表)	空间优化 (滚动变量)
时间复杂度	O(nk)	O(nk)	O(nk)
空间复杂度	O(nk)	O(nk)	O(k)
优势	逻辑与递归一致，好写	消除递归栈开销，性能稳	极致内存利用

5. 总结与分析：解题套路与举一反三

5.1 “至多/恰好/至少” 交易次数的初始化差异

这是区分高级开发者与初学者的关键细节：

• 至多 k 次：dp[0][0][k] 初始化为 0，其余可为 0 或 -inf。因为不一定要完成所有交易。
• 恰好 k 次： 只有起始点 dp[0][0][k] 为 0，所有其他状态（包括 dp[0][0][k-1] 等）必须初始化为 -inf。这确保了最终结果必须从完成 k 次交易的路径推导而来。

5.2 状态机通用模板

1. 定义维度：dp[天数][是否持有][约束维度(如k)]。
2. 确定转移： 绘制状态机，明确每个动作（买、卖、歇）带来的维度变化。
3. 处理偏移： 使用 i+1 映射 i=-1 的基准情形。
4. 空间压缩： 若 dp[i+1] 仅依赖 dp[i]，可舍弃天数维度。

5.3 课后作业与逻辑迁移

通过以下题目巩固“状态机”思维，而非死记硬背：

• LC 714 (手续费): 在卖出时额外减去 fee 即可。
• LC 2786 (访问数组最大分数): 将“当前数字的奇偶性”作为状态机的维度，因为分数加成依赖于上一步的奇偶状态。
• LC 2826 (三组排序): 将“当前属于哪一组 (1, 2, 3)”作为状态，利用状态机处理只能从低组别流向高组别的单向约束。

掌握了状态机 DP，你便能看穿这些题目背后的统一逻辑：万物皆状态，决策即转移。