数据结构与算法 / 系统课时

用状态机处理股票买卖限制

用状态机处理股票买卖限制

股票题一旦同时出现“只能持有一股、卖出后冷冻一天、最多完成若干次交易”,只靠背公式很容易混乱。本节把每天结束时所处的业务阶段直接建成状态,再把交易次数作为额外维度,从状态机统一推导转移规则。

学习目标

  • 把买入、持有、卖出冷冻等业务阶段转换为有限状态
  • 根据合法状态转移推导动态规划递推式,而不是记忆不同题型公式
  • 在存在交易次数上限时,用额外一维记录已完成的交易次数

先把业务限制翻译成状态

以“最多完成 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 卖出得到。

因此递推关系可以写成:

restt′=max(restt,cooldownt)rest'_t = max(rest_t, cooldown_t)
holdt′=max(holdt,restt−p)hold'_t = max(hold_t, rest_t - p)
cooldownt+1′=holdt+pcooldown'_{t+1} = hold_t + p

注意第二式不能使用当天刚从 cooldown 转出的 rest,否则会把“冷冻一天”错误地缩短为零天。实现时应统一从前一天数组计算下一天数组。

用滚动数组实现

下面的实现同时支持冷冻期和最多 k 次交易。不可达状态使用负无穷,避免它们参与后续最大值计算。

python
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))

预期输出

text
3

最优方案可以理解为先在价格 1 买入、价格 2 卖出,经历一天冷冻后再在价格 0 买入、价格 2 卖出,总利润为 3。实际题目若没有冷冻期,可以合并非持股状态;若没有交易次数限制,则可以去掉 t 这一维。

判断什么时候该增加状态维度

遇到新的股票限制时,不要先寻找一条新公式,而应先问:这个限制是否会影响未来允许执行的动作。若答案是会,就应考虑把它加入状态。

例如“最多交易 k 次”需要记录剩余或已完成次数;“是否处于冷冻期”需要记录业务阶段;“每天只能持有一股”则已经被 hold 与非持股状态表达。相反,已经无法影响未来选择的历史细节不应进入状态,否则只会增加复杂度。

这类题真正可复用的不是某组递推式,而是建模方法:先列出未来决策所需的最小状态,再画出合法转移,最后给每条转移附上收益变化。公式只是这个状态机的直接结果。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用状态机处理股票买卖限制

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通