算法►动态规划

状态机 DP：从股票问题理解「有限状态 + 决策转移」

状态机 DP 的本质是：在时间线推进的过程中，用有限个状态描述系统所处阶段，并在状态之间进行合法转移，求全局最优解。股票系列问题是状态机 DP 最经典、也最具迁移价值的模型。

一、什么是状态机 DP

不是“多维 DP”这么简单

状态机 DP 的核心特征

  • 时间维度是线性的（天数 / 下标 i）
  • 状态集合是有限且很小的（通常 2～5 个）
  • 每一天的最优解，只依赖于：
    • 前一天（或前几天）
    • 合法状态之间的转移

典型形式：

1
2
3
dp[i][state] = max / min {
    dp[i-1][prev_state] + cost
}

为什么股票问题天然适合状态机 DP？

因为每天的行为是有限的：

  • 买
  • 卖
  • 什么都不做

而这些行为，本质上只会改变“是否持有股票”这一状态。

二、股票问题的统一状态定义

不管题目怎么变，本质都围绕这两个基础状态：

1
2
state = 0 → 当前不持有股票
state = 1 → 当前持有股票

因此最基础的定义是：

1
dp[i][j] 表示：第 i 天结束后，处于状态 j 时的最大利润

三、基础模型：122 买卖股票的最佳时机 II（无限次交易）

状态定义

1
2
dp[i][0]：第 i 天结束后，不持股的最大利润
dp[i][1]：第 i 天结束后，持股的最大利润

状态转移（状态机视角）

不持股（state = 0）

  • 昨天就不持股，今天什么都不做
  • 昨天持股，今天卖出
1
2
3
4
dp[i][0] = max(
    dp[i-1][0],
    dp[i-1][1] + prices[i]
)

持股（state = 1）

  • 昨天就持股，今天继续持有
  • 昨天不持股，今天买入
1
2
3
4
dp[i][1] = max(
    dp[i-1][1],
    dp[i-1][0] - prices[i]
)

这是最纯粹的状态机 DP 模型，后续所有变形都在此基础上增加约束。

四、加入约束一：冷冻期（309）

买入操作不再只依赖前一天。

卖出后，下一天不能立刻买入，因此：

  • 买入只能从 前两天的不持股状态 转移

状态转移变化

1
2
3
4
5
6
7
8
9
dp[i][0] = max(
    dp[i-1][0],
    dp[i-1][1] + prices[i]
)

dp[i][1] = max(
    dp[i-1][1],
    dp[i-2][0] - prices[i]
)

这类题的本质不是“新增状态”，而是：转移来源发生了变化

五、加入约束二：交易次数限制（188 / 123）

为什么要引入「交易次数」维度？

因为一次完整交易 = 买入 + 卖出
限制交易次数，意味着 dp 数组中必须记录“还剩几次卖出的机会”。

状态定义（标准三维状态机）

1
2
3
4
5
dp[i][k][j]
表示：第 i 天结束后，
      还剩 k 次交易机会，
      当前状态为 j（0 不持股 / 1 持股）
      的最大利润

核心转移逻辑（只在卖出时消耗交易次数）

1
2
3
4
5
6
7
8
9
dp[i][k][0] = max(
    dp[i-1][k][0],
    dp[i-1][k-1][1] + prices[i]
)

dp[i][k][1] = max(
    dp[i-1][k][1],
    dp[i-1][k][0] - prices[i]
)

为什么是卖出时 k-1，而不是买入？
因为一次交易以“完成卖出”为标志。理论上由于最后一天不持有股票的价值一定最高，所以买入时进行 k-1 也可以。

121 / 123 与 188 的关系

题目 本质
121 k = 1 的特例（可用贪心优化）
123 k = 2 的特例
188 任意 k 的通用模型

六、加入约束三：手续费（714）

本质变化

每一笔交易都会多付出一个固定成本。

手续费只影响 买入或卖出其中一个时机，常见处理方式：

在买入时扣手续费

1
2
3
4
dp[i][1] = max(
    dp[i-1][1],
    dp[i-1][0] - prices[i] - fee
)

或在卖出时扣手续费（等价）

1
2
3
4
dp[i][0] = max(
    dp[i-1][0],
    dp[i-1][1] + prices[i] - fee
)

七、状态机 DP 的工程级总结

建模顺序

  1. 时间轴是什么？（天数 / 下标）
  2. 系统有哪些有限状态？（股票的持有与否）
  3. 哪些状态之间可以互相转移？（持有股票通过当天卖出转化为未持有）
  4. 哪些转移有额外约束？（手续费、交易次数限制）

股票状态机的通用模板

1
2
3
4
5
for i in [0..n):
    for state in States:
        dp[i][state] = max(
            from all valid prev_state
        )

状态机 DP 变形

  • 可迁移到时机开发中：订单状态流转、流控 / 限流、工作流引擎、资源占用 / 释放建模

这是后端系统里“时间 + 状态”的通用建模方式。

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。