最佳买卖股票时机含冷冻期

问题拆解

不限交易次数地买卖股票，但卖出后的第二天是冷冻期，不能买入，求最大利润。没有冷冻期时，普通的“持有 / 空仓”两状态 DP 就够了；冷冻期打破了这个划分——同样是手里没股票，“昨天刚卖掉”和“已经空仓一天以上”待遇不同：前者今天不能买，后者可以。

所以把状态拆成三个，都定义为“第 i 天结束时”的最大利润：

hold：手里持有股票；
sold：今天刚卖出（明天进入冷冻期）；
rest：空仓且不处于冷冻，明天可以买。

转移方程按“今天做了什么”推：

hold[i] = max(hold[i-1], rest[i-1] - prices[i])  // 继续持有，或今天买入（只能从 rest 买）
sold[i] = hold[i-1] + prices[i]                   // 今天卖出，昨天必须持有
rest[i] = max(rest[i-1], sold[i-1])               // 继续观望，或冷冻期刚结束

状态怎么分不看手里有没有股票，而看“明天允许做什么”——sold 和 rest 手里都没股票，区别只在下一步的行动集合。

三状态机滚动变量

每天的状态只依赖前一天，三个变量滚动即可。初始化：第 0 天买入则 hold = -prices[0]，sold 和 rest 都是 0（第 0 天“刚卖出”不可能发生，设为 0 不影响后续取 max）。答案是最后一天 sold 和 rest 的较大者——最优解结束时不该还拿着股票。

public int maxProfit(int[] prices) {
    int hold = -prices[0]; // 持有股票
    int sold = 0;          // 今天刚卖出，明天冷冻
    int rest = 0;          // 空仓且可买
    for (int i = 1; i < prices.length; i++) {
        int prevHold = hold, prevSold = sold, prevRest = rest; // 全部用昨天的值
        hold = Math.max(prevHold, prevRest - prices[i]); // 只能从 rest 买入
        sold = prevHold + prices[i];
        rest = Math.max(prevRest, prevSold);
    }
    return Math.max(sold, rest);
}

def maxProfit(prices: List[int]) -> int:
    hold = -prices[0]  # 持有股票
    sold = 0           # 今天刚卖出，明天冷冻
    rest = 0           # 空仓且可买

    for price in prices[1:]:
        hold, sold, rest = (
            max(hold, rest - price),  # 只能从 rest 买入
            hold + price,
            max(rest, sold),
        )

    return max(sold, rest)

func maxProfit(prices []int) int {
    hold := -prices[0] // 持有股票
    sold := 0          // 今天刚卖出，明天冷冻
    rest := 0          // 空仓且可买
    for _, price := range prices[1:] {
        hold, sold, rest = max(hold, rest-price), hold+price, max(rest, sold)
    }
    return max(sold, rest)
}

pub fn max_profit(prices: Vec<i32>) -> i32 {
    let mut hold = -prices[0]; // 持有股票
    let mut sold = 0; // 今天刚卖出，明天冷冻
    let mut rest = 0; // 空仓且可买
    for &price in &prices[1..] {
        let new_hold = hold.max(rest - price); // 只能从 rest 买入
        let new_sold = hold + price;
        let new_rest = rest.max(sold);
        hold = new_hold;
        sold = new_sold;
        rest = new_rest;
    }
    sold.max(rest)
}

滚动更新时最容易错的就是新旧值混用：三条转移全部引用昨天的状态，所以必须像 Rust 版那样先把三个新值都算出来再一起赋值（Python 和 Go 的多重赋值天然做到了这一点）。比如 rest 的转移用的是昨天的 sold，如果先更新了 sold 再算 rest，就等于允许“今天卖出、今天又算作可买”，冷冻期被吃掉了。同理 hold 里减价格的必须是昨天的 rest 而不是 sold——刚卖完的第二天不能买，这正是这道题与普通买卖股票唯一的差别。

复杂度

指标	复杂度	原因
时间	`O(n)`	每天做常数次转移
空间	`O(1)`	三个滚动变量

可以迁移的模式

带约束的序列决策先画状态机：枚举“今天结束时的处境”，再枚举“今天能做的动作”连边；
约束（冷冻期、手续费、交易次数）通常体现为状态的进一步细分或转移边的删减，而不是全新的算法；
滚动更新多个互相依赖的状态时，先算全部新值再统一赋值，避免用到“今天”的数据。

整个股票系列（121、122、123、188、309、714）都是同一台状态机换不同的约束，把这台三状态的搭起来，其余的只是加减状态。