30 秒速览
- 核心思想：用状态表示当前处境，状态之间有转换规则
- 典型场景：股票交易（持有/不持有）、限次操作
- 状态定义：
dp[i][state]= 第 i 天处于 state 状态时的最优值 - 转移方式：根据动作在状态之间转移
一、直觉建立
什么是状态机？
想象一个自动售货机：
[空闲] --投币--> [已付款] --选择商品--> [出货] --取货--> [空闲]
它有几个状态，在不同状态下可以做不同的动作，动作会让状态转换。
股票问题的状态机
买卖股票有两种基本状态：
买入 卖出
[不持有] ------> [持有] -------> [不持有]
^ |
|_______________________________|
为什么用状态机 DP？
普通 DP 难以处理：
- 有限制条件的转换（卖出后第二天才能买）
- 多种状态互相影响
- 交易次数限制
状态机 DP 把这些明确建模成状态和转移。
二、股票问题总览
| 题号 | 题目 | 特点 |
|---|---|---|
| 121 | 买卖股票 I | 只能交易 1 次 |
| 122 | 买卖股票 II | 无限次交易 |
| 123 | 买卖股票 III | 最多 2 次交易 |
| 188 | 买卖股票 IV | 最多 k 次交易 |
| 309 | 买卖股票 V | 冷冻期 |
| 714 | 买卖股票 VI | 手续费 |
三、典型例题
例题 1：LC 121. 买卖股票的最佳时机
题目：只能完成一笔交易，求最大利润。
贪心解法
记录最低价格，计算每天卖出的利润。
def maxProfit(prices: list[int]) -> int:
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
复杂度：时间 O(n)，空间 O(1)
例题 2：LC 122. 买卖股票的最佳时机 II
题目：可以完成多笔交易，求最大利润。
贪心解法
只要有利润就交易。
def maxProfit(prices: list[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
状态机 DP
def maxProfit(prices: list[int]) -> int:
n = len(prices)
# hold[i] = 第 i 天结束时持有股票的最大利润
# cash[i] = 第 i 天结束时不持有股票的最大利润
hold = [0] * n
cash = [0] * n
hold[0] = -prices[0]
cash[0] = 0
for i in range(1, n):
# 持有：昨天持有，或今天买入
hold[i] = max(hold[i-1], cash[i-1] - prices[i])
# 不持有：昨天不持有，或今天卖出
cash[i] = max(cash[i-1], hold[i-1] + prices[i])
return cash[n-1]
空间优化：
def maxProfit(prices: list[int]) -> int:
hold = -prices[0]
cash = 0
for price in prices[1:]:
hold = max(hold, cash - price)
cash = max(cash, hold + price)
return cash
例题 3：LC 123. 买卖股票的最佳时机 III
题目：最多完成 2 笔交易。
状态机 DP
4 种状态：
buy1：第一次买入后sell1：第一次卖出后buy2：第二次买入后sell2：第二次卖出后
def maxProfit(prices: list[int]) -> int:
buy1 = buy2 = -prices[0]
sell1 = sell2 = 0
for price in prices[1:]:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2
复杂度：时间 O(n)，空间 O(1)
例题 4：LC 188. 买卖股票的最佳时机 IV
题目：最多完成 k 笔交易。
状态机 DP
def maxProfit(k: int, prices: list[int]) -> int:
n = len(prices)
if n <= 1 or k == 0:
return 0
# 如果 k >= n/2，相当于无限次交易
if k >= n // 2:
profit = 0
for i in range(1, n):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
# 状态机 DP
# buy[j] = 第 j 次买入后的最大利润
# sell[j] = 第 j 次卖出后的最大利润
buy = [-float('inf')] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j-1] - price)
sell[j] = max(sell[j], buy[j] + price)
return sell[k]
复杂度：时间 O(nk)，空间 O(k)
例题 5：LC 309. 最佳买卖股票时机含冷冻期
题目：卖出后有一天冷冻期，不能立即买入。
状态机
3 种状态：
hold：持有股票cash：不持有，不在冷冻期cooldown：不持有，在冷冻期（刚卖出）
def maxProfit(prices: list[int]) -> int:
if not prices:
return 0
hold = -prices[0]
cash = 0
cooldown = 0
for price in prices[1:]:
new_hold = max(hold, cash - price)
new_cash = max(cash, cooldown)
new_cooldown = hold + price
hold, cash, cooldown = new_hold, new_cash, new_cooldown
return max(cash, cooldown)
状态转换图：
买入 卖出
[cash] ------> [hold] ------> [cooldown]
^ |
|_______________________________|
冷冻期结束
复杂度：时间 O(n)，空间 O(1)
例题 6：LC 714. 买卖股票的最佳时机含手续费
题目：每次交易有手续费。
状态机 DP
def maxProfit(prices: list[int], fee: int) -> int:
hold = -prices[0]
cash = 0
for price in prices[1:]:
hold = max(hold, cash - price)
cash = max(cash, hold + price - fee) # 卖出时扣除手续费
return cash
复杂度：时间 O(n)，空间 O(1)
四、状态机 DP 模板
基本框架
def state_machine_dp(prices):
# 定义状态
state1 = 初始值1
state2 = 初始值2
...
for price in prices:
# 计算新状态（注意用临时变量或同时更新）
new_state1 = max(state1, 从其他状态转换)
new_state2 = max(state2, 从其他状态转换)
...
state1, state2, ... = new_state1, new_state2, ...
return 最终状态
状态定义技巧
- “持有"状态：初始化为
-prices[0]（买入第一天的股票） - “不持有"状态：初始化为
0 - 第 j 次交易：依赖第 j-1 次的结果
五、其他状态机 DP 问题
例题 7：LC 198. 打家劫舍
题目：不能偷相邻的房子，求最大金额。
状态机 DP
两种状态：
rob[i]= 偷第 i 个房子的最大金额not_rob[i]= 不偷第 i 个房子的最大金额
def rob(nums: list[int]) -> int:
if not nums:
return 0
rob = nums[0]
not_rob = 0
for num in nums[1:]:
new_rob = not_rob + num
new_not_rob = max(rob, not_rob)
rob, not_rob = new_rob, new_not_rob
return max(rob, not_rob)
复杂度：时间 O(n)，空间 O(1)
例题 8：LC 213. 打家劫舍 II
题目：房子排成环（首尾相连）。
思路
分成两种情况：
- 偷第一个房子，不偷最后一个
- 不偷第一个房子，可以偷最后一个
def rob(nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
def rob_range(arr):
rob, not_rob = 0, 0
for num in arr:
rob, not_rob = not_rob + num, max(rob, not_rob)
return max(rob, not_rob)
# 情况 1：不偷最后一个
# 情况 2：不偷第一个
return max(rob_range(nums[:-1]), rob_range(nums[1:]))
六、常见错误与陷阱
错误 1：状态更新顺序
# 错误：用已更新的值计算
hold = max(hold, cash - price)
cash = max(cash, hold + price) # 用了新的 hold！
# 正确：用临时变量或同时计算
new_hold = max(hold, cash - price)
new_cash = max(cash, hold + price)
hold, cash = new_hold, new_cash
错误 2：初始值错误
# 持有状态初始化
hold = -prices[0] # 正确：第一天买入
hold = 0 # 错误：没花钱
# 不持有状态初始化
cash = 0 # 正确
cash = -prices[0] # 错误
错误 3：冷冻期状态遗漏
# 冷冻期问题有 3 种状态，不是 2 种
# hold, cash, cooldown
错误 4：手续费位置
# 买入时扣
hold = max(hold, cash - price - fee)
# 卖出时扣（常见）
cash = max(cash, hold + price - fee)
# 两种都行，但要一致
七、复盘清单
触发信号
- 多次操作/交易
- 操作有限制（相邻不能、冷冻期）
- 有多种互斥状态
- 操作有代价（手续费）
状态定义
- 状态是否完整（覆盖所有情况）
- 状态转换是否正确
- 初始值是否正确
实现检查
- 状态更新顺序（用临时变量）
- 边界条件（空输入、单元素）
- 返回值（最终状态）
八、题目清单
股票系列
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 121 | 买卖股票 I | Easy | 单次交易 |
| 122 | 买卖股票 II | Medium | 无限次 |
| 123 | 买卖股票 III | Hard | 2 次交易 |
| 188 | 买卖股票 IV | Hard | k 次交易 |
| 309 | 买卖股票 V | Medium | 冷冻期 |
| 714 | 买卖股票 VI | Medium | 手续费 |
其他状态机
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 198 | 打家劫舍 | Medium | 2 状态 |
| 213 | 打家劫舍 II | Medium | 环形 |
| 337 | 打家劫舍 III | Medium | 树形 DP |
| 152 | 乘积最大子数组 | Medium | 正负状态 |