动态规划中等1 种解法

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

交易次数不限，但卖出后的下一天不能买入，求最大利润。

#数组#动态规划#状态机#股票

解题主线

每天结束时严格区分休息、持股、当天卖出三种状态；只有前一天处于休息状态，今天才能买入。

今天的休息状态可来自昨天继续休息或昨天卖出，后者经过今天后才解除冷冻。

当天卖出必须来自昨天持股，不能从今天刚买入的状态转移。

解法 1：三状态动态规划

维护 rest（不持股且今天未卖出）、hold（持股）和 sold（今天卖出）；买入只能从前一天 rest 转移，从而自然落实一天冷冻期。

时间复杂度

O(n)

空间复杂度

O(1)

309. 买卖股票的最佳时机含冷冻期 · 三状态动态规划

java

final class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int rest = 0;
        int hold = -prices[0];
        int sold = Integer.MIN_VALUE;

        for (int i = 1; i < prices.length; i++) {
            int previousRest = rest;
            int previousHold = hold;
            int previousSold = sold;

            rest = Math.max(previousRest, previousSold);
            hold = Math.max(previousHold, previousRest - prices[i]);
            sold = previousHold + prices[i];
        }
        return Math.max(rest, sold);
    }
}

维护 rest（不持股且今天未卖出）、hold（持股）和 sold（今天卖出）；买入只能从前一天 rest 转移，从而自然落实一天冷冻期。

Integer.MIN_VALUE 只用于首日不可达的 sold；后续 sold 始终由可达的 hold 加价格得到，不会发生哨兵加法溢出。

边界与易错点

旧 Q188_maxStockProfit_frozen 实际属于题号 309，且状态注释与转移方程错位；例如 [2, 1] 会错误返回 1，不能直接保留。
休息状态不是“当天处于冷冻期”的同义词：它表示今天没有卖出且不持股，下一天允许买入。
当天卖出状态在第 0 天不可达，应使用负无穷哨兵而不是 0，避免状态语义被放宽。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q188_maxStockProfit_frozen.javaleetcode/src/main/java/greedy/Q309_maxStockProfit_frozen.java