算法刷题系列（五十一）：状态机 DP——用有限状态表达阶段变化

算法刷题系列（五十一）：状态机 DP——用有限状态表达阶段变化

有些优化问题不仅受“处理到第几个元素”影响，还受当前处于哪个阶段影响。例如买卖股票时，今天结束后可能是空仓，也可能持有股票。状态机 DP 把阶段显式列出来，再为每种合法状态写出来自前一天的转移。

本文考虑一个简化交易模型：每天最多进行一次买入或卖出，任意时刻最多持有一股，不收手续费，卖出后可以在之后的天再次买入。目标是最大化利润。

一、定义两个状态

处理完第 i 天后：

• cash[i]：不持有股票时能取得的最大利润；
• hold[i]：持有一股股票时能取得的最大利润。

今天结束时不持股，可以昨天就空仓，或今天卖出昨天持有的股票：

cash[i] = max(cash[i - 1], hold[i - 1] + price[i])

今天结束时持股，可以昨天已持有，或今天用空仓状态买入：

hold[i] = max(hold[i - 1], cash[i - 1] - price[i])

右侧都使用昨天的状态，确保同一天不会在一次更新中同时买入并卖出。

二、初始化与例子

开始交易前，空仓利润为 0，持仓状态不可达。用很小的负数表示不可达，或直接把第一天初始化为：

cash = 0
hold = -price[0]

价格为 [3, 1, 4, 2, 6] 时，先在价格 1 买入，再以 4 卖出，之后在 2 买入并以 6 卖出，总利润为 3 + 4 = 7。

状态只记录各自阶段中最优的利润。若两条历史路径到达同一阶段，较低利润的路径不会帮助后续取得更高利润，可以保留较大值。

三、正确性说明

每天结束时的持仓情况只有“持有”与“空仓”两种。对空仓状态，最后一步只能是保持空仓或当天卖出；对持仓状态，最后一步只能是保持持仓或当天买入。两个转移恰好枚举了所有合法最后动作，并且都从前一日合法状态出发。因此逐日归纳，cash 和 hold 分别保存当天两个阶段的最大可达利润。交易结束要求不持股，返回 cash。

四、Java 实现

public class StateMachineDp {
    public static long maxProfit(int[] prices) {
        if (prices == null) {
            throw new IllegalArgumentException("prices must not be null");
        }
        if (prices.length == 0) {
            return 0;
        }

        long cash = 0;
        long hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            long oldCash = cash;
            long oldHold = hold;
            cash = Math.max(oldCash, oldHold + prices[i]);
            hold = Math.max(oldHold, oldCash - prices[i]);
        }
        return cash;
    }

    public static void main(String[] args) {
        if (maxProfit(new int[]{3, 1, 4, 2, 6}) != 7
                || maxProfit(new int[]{5, 4, 3}) != 0
                || maxProfit(new int[]{}) != 0) {
            throw new AssertionError("state machine test failed");
        }
    }
}

保存 oldCash 和 oldHold 是为了让两条更新都读取前一天的状态。也可以先计算两个新变量，再一起赋回。

五、Python 实现

def max_profit(prices):
    if prices is None:
        raise ValueError("prices must not be None")
    if not prices:
        return 0

    cash = 0
    hold = -prices[0]
    for price in prices[1:]:
        old_cash = cash
        old_hold = hold
        cash = max(old_cash, old_hold + price)
        hold = max(old_hold, old_cash - price)
    return cash

assert max_profit([3, 1, 4, 2, 6]) == 7
assert max_profit([5, 4, 3]) == 0
assert max_profit([8]) == 0
assert max_profit([]) == 0

六、复杂度与变化规则

每一天只更新两个状态，时间复杂度 O(n)；只保存前一天，额外空间 O(1)。如果题目增加限制，例如只能完成一次交易、卖出后必须冷冻一天、最多交易 k 次或每笔交易收手续费，就应新增或调整状态，而不是在原有转移上临时拼条件。

举例说，冷冻期可以添加“今天刚卖出”的状态，或保存前两天的空仓状态；手续费可在卖出转移时扣除。状态数来自题目的阶段规则，不应凭经验随意设定。

七、边界与常见错误

1. 初始化持仓为 0：这相当于免费得到股票，会虚增利润。
2. 返回 hold：题意通常要求交易结束后空仓，应返回 cash。
3. 原地更新破坏旧状态：第二条转移读取的可能已是今天更新后的状态；使用临时变量最清楚。
4. 忽略空输入：没有交易日时利润为 0。
5. 把模型规则混在一起：能否当天买卖、手续费何时扣、交易次数如何限制，都要从题意明确，不同规则有不同转移。
6. 把不可达当成普通数值：复杂扩展状态中，应使用足够小的哨兵值，并避免对哨兵做可能溢出的运算。

小结

状态机 DP 把“阶段”纳入状态定义。先列出处理完当前元素后的所有互斥状态，再枚举每个状态的合法来源。交易例子中，空仓与持仓两态构成有限状态机，日更转移后只需常数空间。