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

题目描述

给定一个整数数组 prices，其中 prices[i] 表示第 i 天股票的价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易：

你可以多次买卖一支股票
你不能同时参与多笔交易，也就是说再次购买前必须先卖出之前的股票
卖出股票后，你无法在第二天买入股票（即冷冻期为 1 天）

返回你能获得的最大利润。

示例分析

示例 1

输入: prices = [1,2,3,0,2]
输出: 3

一种最优操作方式是：

第 1 天买入
第 3 天卖出
第 4 天冷冻
第 5 天买入并卖出

更准确地按下标从 0 开始写就是：

第 0 天买入，价格 1
第 2 天卖出，价格 3，利润为 2
第 3 天处于冷冻期，不能买
第 4 天买入再卖出在这题里不成立，因为同一天不能又买又卖

所以真正的最优路径是：

第 0 天买入，价格 1
第 1 天卖出，价格 2，利润 1
第 2 天冷冻
第 3 天买入，价格 0
第 4 天卖出，价格 2，利润 2

总利润：

1 + 2 = 3

解题思路

这道题本质上仍然是一道股票类动态规划题。

如果没有冷冻期，那么我们通常只需要考虑：

今天手里没有股票
今天手里有股票

但这道题多了一个条件：

卖出后的第二天不能买入

这就意味着，“今天想买入”时，不能直接从“昨天没持股”的状态转移过来，必须确保昨天不是刚卖出。

而你给出的这份代码，正是通过一个非常巧妙的状态设计，把这个“冷冻期”自然地融进了转移方程中。

代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 2][2];
        f[1][1] = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            f[i + 2][0] = Math.max(f[i + 1][0], f[i + 1][1] + prices[i]);
            f[i + 2][1] = Math.max(f[i + 1][1], f[i][0] - prices[i]);
        }
        return f[n + 1][0];
    }
}

这份代码的写法很简洁，但第一次看时最容易疑惑的是：

f[i][0] 和 f[i][1] 分别表示什么
为什么买入转移时用的是 f[i][0] - prices[i]，而不是更常见的 f[i + 1][0] - prices[i]
n + 2 这个偏移是怎么来的

下面一步一步讲清楚。

状态定义

我们定义：

f[i][0] 表示：考虑完前 i-1 天后，手里没有股票时的最大利润
f[i][1] 表示：考虑完前 i-1 天后，手里持有股票时的最大利润

这里有一个偏移量设计：

f[2] 对应处理完第 0 天
f[3] 对应处理完第 1 天
…
f[i + 2] 对应处理完第 i 天

这就是为什么代码里用了：

f[i + 2][...]

这种写法虽然看起来有点绕，但它有一个很大的好处：

可以非常自然地写出“买入时回看前两天”的转移，从而处理冷冻期。

两个状态分别表示什么

1. `f[i][0]`：当前不持股

表示到了某一天结束后，手里没有股票时，能得到的最大利润。

当前不持股有两种可能：

之前就不持股，今天什么都不做
之前持股，今天把股票卖掉了

2. `f[i][1]`：当前持股

表示到了某一天结束后，手里持有股票时，能得到的最大利润。

当前持股也有两种可能：

之前就持股，今天什么都不做
今天买入股票

但注意：今天买入时必须避开冷冻期。

这正是这道题的核心。

状态转移方程

一、不持股状态

f[i + 2][0] = Math.max(f[i + 1][0], f[i + 1][1] + prices[i]);

处理第 i 天后，如果不持股，有两种来源：

情况 1：昨天也不持股，今天休息

f[i + 1][0]

情况 2：昨天持股，今天卖出

f[i + 1][1] + prices[i]

因为卖出股票会获得 prices[i] 的收益。

所以取两者最大值。

二、持股状态

f[i + 2][1] = Math.max(f[i + 1][1], f[i][0] - prices[i]);

处理第 i 天后，如果持股，也有两种来源：

情况 1：昨天就持股，今天继续持有

f[i + 1][1]

情况 2：今天买入

这时最关键。

如果今天买入，由于卖出后第二天不能买，所以昨天不能是“刚卖完”。因此今天买入时，能转移过来的状态必须是：

至少隔一天之前的不持股状态

也就是代码中的：

f[i][0] - prices[i]

这里 f[i][0] 对应的是“处理完第 i-2 天后不持股的最大利润”。

这样就自动绕开了第 i-1 天，确保如果第 i-1 天是卖出日，那么第 i 天不会非法买入。

这就是冷冻期在状态转移中的体现。

为什么买入要看 `f[i][0]`

这是整道题最重要的地方。

很多人一开始会下意识写成：

f[i + 1][0] - prices[i]

也就是从“昨天不持股”转移到“今天持股”。

但这在本题是不对的，因为：

昨天不持股，可能是因为昨天刚卖出
如果昨天刚卖出，那么今天处于冷冻期，不能买入

所以不能直接从昨天的不持股状态买入。

必须回退一天，用：

f[i][0]

也就是“前天结束时不持股”的状态。

这样就把昨天空出来了，刚好满足“卖出后第二天不能买”的限制。

初始化为什么这样写

代码里有一句：

f[1][1] = Integer.MIN_VALUE;

这表示：

在还没有开始处理任何实际交易日之前，持股状态是不合法的

因为不可能在“第 -1 天结束后”手里就已经有股票。

所以把它初始化成一个极小值，表示这种状态不可达。

而 f[*][0] 默认初始化为 0，表示一开始不持股时利润为 0。

代码解析

1. 获取天数并定义 DP 数组

int n = prices.length;
int[][] f = new int[n + 2][2];

开 n + 2 的目的就是为了给状态转移留出偏移空间，让 f[i]、f[i + 1]、f[i + 2] 的关系写起来更顺。

2. 初始化非法持股状态

f[1][1] = Integer.MIN_VALUE;

表示在最开始这个阶段，持股不可能发生。

3. 遍历每一天

for (int i = 0; i < n; i++) {

这里 i 表示当前处理的是第 i 天，股票价格是 prices[i]。

4. 更新不持股状态

f[i + 2][0] = Math.max(f[i + 1][0], f[i + 1][1] + prices[i]);

不动
或者卖出

5. 更新持股状态

f[i + 2][1] = Math.max(f[i + 1][1], f[i][0] - prices[i]);

不动
或者买入，但买入时要跳过一天，体现冷冻期

6. 返回最后一天结束后的不持股利润

return f[n + 1][0];

最终答案一定是“不持股”状态。

因为如果最后还持有股票，说明还没卖掉，利润不完整。

示例推演

我们用经典例子：

prices = [1,2,3,0,2]

来简单推演一下。

第 0 天，价格 1

不持股：0
持股：-1

第 1 天，价格 2

不持股：max(昨天不持股, 昨天持股今天卖)
```
max(0, -1 + 2) = 1
```
持股：max(昨天持股, 前天空仓今天买)
```
max(-1, 0 - 2) = -1
```

第 2 天，价格 3

不持股：
```
max(1, -1 + 3) = 2
```
持股：
```
max(-1, 0 - 3) = -1
```

第 3 天，价格 0

不持股：
```
max(2, -1 + 0) = 2
```
持股：这里关键是不能从“昨天刚卖完”的状态买入，所以看前天空仓：
```
max(-1, 1 - 0) = 1
```

第 4 天，价格 2

不持股：
```
max(2, 1 + 2) = 3
```
持股：
```
max(1, 2 - 2) = 1
```

最终答案：

这就是题目给出的结果。

为什么最后必须返回不持股状态

这点很容易理解。

题目要求的是最大利润。如果最后一天结束时你手里还拿着股票，那说明这支股票还没有卖掉，这部分价值并没有真正兑现成利润。

所以最后答案只能取：

f[n + 1][0]

也就是最后一天结束后不持股时的最大利润。

和三状态写法对比

这道题还有一种很常见的写法，会把状态拆成三类：

持股
不持股且今天卖出
不持股且今天处于冷冻 / 休息状态

那种写法更直观一点，因为会把“冷冻期”显式表示出来。

而你这份代码更巧妙，它没有额外开第三种状态，而是通过：

f[i][0] - prices[i]

这种“回看前两天”的方式，把冷冻期隐含在转移里。

三状态写法的优点

状态意义更直观
更适合第一次理解题目

当前两状态偏移写法的优点

状态更精炼
代码更短
冷冻期通过下标关系自然体现出来

所以你这份写法是很漂亮的一种 DP 实现。

复杂度分析

设数组长度为 n。

时间复杂度

O(n)

只遍历了一次数组。

空间复杂度

O(n)

使用了一个 n + 2 大小的二维数组。

如果进一步优化，其实还可以把空间压缩到 O(1)，因为每次只依赖前面有限几个状态。

总结

这道题的核心在于：

冷冻期会影响“买入”这个动作，所以买入时不能直接从昨天的不持股状态转移，而必须跳过一天。

也就是说：

不持股时，要么休息，要么今天卖出
持股时，要么继续持有，要么今天买入
但今天买入时，必须从“前天不持股”的状态转移过来

这就是为什么代码里写的是：

f[i + 2][1] = Math.max(f[i + 1][1], f[i][0] - prices[i]);

你可以把这题记成一句话：

冷冻期的本质，就是“卖出后的第二天不能买”，所以买入时要往前多看一天。

这是一道非常经典的股票 DP 题，把这题真正吃透之后，股票系列很多题都会变得更容易理解。