数据结构与算法 / 系统课时
用状态机处理股票买卖限制
用状态机处理股票买卖限制
股票题一旦同时出现“只能持有一股、卖出后冷冻一天、最多完成若干次交易”,只靠背公式很容易混乱。本节把每天结束时所处的业务阶段直接建成状态,再把交易次数作为额外维度,从状态机统一推导转移规则。
学习目标
- 把买入、持有、卖出冷冻等业务阶段转换为有限状态
- 根据合法状态转移推导动态规划递推式,而不是记忆不同题型公式
- 在存在交易次数上限时,用额外一维记录已完成的交易次数
先把业务限制翻译成状态
以“最多完成 k 次交易,并且卖出后冷冻一天”为例。一天结束时,与后续决策真正有关的不是完整交易历史,而是当前属于哪一种阶段。
可以定义三个状态:rest 表示当天结束时没有持股且当天没有卖出;hold 表示当天结束时持有一股;cooldown 表示当天刚刚卖出,因此下一天不能立即买入。

状态机最重要的作用是排除非法操作。例如 cooldown 不能直接转到 hold,因为这相当于卖出后的第二天立即买入;它必须先经过一天,转成 rest。
从状态机写出转移
再加入交易次数 t,表示已经完成的卖出次数。买入只是建立持仓,不算完成一笔交易;只有卖出时,t 才增加 1。
设今天价格为 p,前一天三个状态分别为 rest[t]、hold[t]、cooldown[t]。当天的合法转移是:
rest[t]可以继续休息,也可以由上一天的cooldown[t]结束冷冻后进入。hold[t]可以继续持有,也可以从上一天的rest[t]花费p买入。cooldown[t + 1]只能由上一天的hold[t]以价格p卖出得到。
因此递推关系可以写成:
注意第二式不能使用当天刚从 cooldown 转出的 rest,否则会把“冷冻一天”错误地缩短为零天。实现时应统一从前一天数组计算下一天数组。
用滚动数组实现
下面的实现同时支持冷冻期和最多 k 次交易。不可达状态使用负无穷,避免它们参与后续最大值计算。
from math import inf
def max_profit(prices: list[int], k: int) -> int:
if not prices or k <= 0:
return 0
rest = [-inf] * (k + 1)
hold = [-inf] * (k + 1)
cooldown = [-inf] * (k + 1)
# 第一天结束时:可以什么都不做,也可以买入第一股。
rest[0] = 0
hold[0] = -prices[0]
for price in prices[1:]:
next_rest = [-inf] * (k + 1)
next_hold = [-inf] * (k + 1)
next_cooldown = [-inf] * (k + 1)
for t in range(k + 1):
next_rest[t] = max(rest[t], cooldown[t])
next_hold[t] = max(hold[t], rest[t] - price)
# 卖出后才算完成一笔交易,因此交易次数增加 1。
if t < k and hold[t] != -inf:
next_cooldown[t + 1] = hold[t] + price
rest, hold, cooldown = next_rest, next_hold, next_cooldown
# 最终利润必须来自未持股状态。
return int(max(max(rest), max(cooldown), 0))
prices = [1, 2, 3, 0, 2]
print(max_profit(prices, 2))预期输出
3最优方案可以理解为先在价格 1 买入、价格 2 卖出,经历一天冷冻后再在价格 0 买入、价格 2 卖出,总利润为 3。实际题目若没有冷冻期,可以合并非持股状态;若没有交易次数限制,则可以去掉 t 这一维。
判断什么时候该增加状态维度
遇到新的股票限制时,不要先寻找一条新公式,而应先问:这个限制是否会影响未来允许执行的动作。若答案是会,就应考虑把它加入状态。
例如“最多交易 k 次”需要记录剩余或已完成次数;“是否处于冷冻期”需要记录业务阶段;“每天只能持有一股”则已经被 hold 与非持股状态表达。相反,已经无法影响未来选择的历史细节不应进入状态,否则只会增加复杂度。
这类题真正可复用的不是某组递推式,而是建模方法:先列出未来决策所需的最小状态,再画出合法转移,最后给每条转移附上收益变化。公式只是这个状态机的直接结果。