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

发表于 分类于 阅读次数： Waline： 本文字数： 884 阅读时长 ≈ 3 分钟

考点

  • 状态机DP

思路

一、问题核心约束抽象

给定股票价格数组 prices[0..n-1]，允许多次买卖，但有一个关键限制：

每次卖出后，必须冷冻 1 天，冷冻期内不能买入。

因此时间维度上的状态并不是“只有持股 / 不持股”这么简单，而是至少需要区分：

  • 不持股但 可以买
  • 不持股但 不能买（冷冻期）
  • 正在持股

这正是 3 状态 DP 的来源。

二、状态定义（最关键）

设： \[ f[i][j] \] 表示：处理完前 \(i\) 天（即考虑到 prices[i-1] 为止）后，处于状态 \(j\) 时的最大收益。

定义三个互斥状态：

状态 含义
\(f[i][0]\) 第 \(i\) 天结束后：不持股，且不处于冷冻期（可买）
\(f[i][1]\) 第 \(i\) 天结束后：持股
\(f[i][2]\) 第 \(i\) 天结束后：不持股，且处于冷冻期（今天刚卖）

注意： 冷冻期只能由 “昨天持股，今天卖出” 产生，这是本题最关键的单向约束。

三、初始值（边界条件）

第 0 天表示：还未进行任何交易。 \[ \begin{aligned} f[0][0] &= 0 \quad &\text{(空仓，可买)} \\ f[0][1] &= -\infty \quad &\text{(不可能一开始就持股)} \\ f[0][2] &= -\infty \quad &\text{(不可能一开始就在冷冻期)} \end{aligned} \] 代码中通常用一个极小负数代替 \(-\infty\)：

1
2
f[0][0] = 0;
f[0][1] = f[0][2] = neg;

四、状态转移方程（完整且严格合法）

设当前处理第 \(i\) 天，对应价格为： \[ price = prices[i-1] \]

1️⃣ 空仓且不在冷冻期（可买）

\[ f[i][0] \]

今天仍然保持“可买空仓”只有两种合法来源：

  • 昨天已经是可买空仓
  • 昨天是冷冻期，今天冷冻结束

\[ \boxed{ f[i][0] = \max\left( f[i-1][0],\; f[i-1][2] \right) } \]

2️⃣ 持股状态

\[ f[i][1] \]

今天想要持股，也只有两种合法来源：

  • 昨天已经持股，继续持有
  • 昨天是「可买空仓」，今天买入

⚠️ 不能从冷冻状态买入，否则就违反了题目规则。 \[ \boxed{ f[i][1] = \max\left( f[i-1][1],\; f[i-1][0] - price \right) } \]

3️⃣ 冷冻期状态（今天刚卖）

\[ f[i][2] \]

今天处于冷冻期 只有一种来源：

  • 昨天必须是持股状态，今天卖出

\[ \boxed{ f[i][2] = f[i-1][1] + price } \]

✅ 三个状态的完整转移汇总

\[ \begin{aligned} f[i][0] &= \max\left( f[i-1][0],\; f[i-1][2] \right) \\ f[i][1] &= \max\left( f[i-1][1],\; f[i-1][0] - prices[i-1] \right) \\ f[i][2] &= f[i-1][1] + prices[i-1] \end{aligned} \]

五、最终答案的选择

最后一天结束时：

  • 若持股 \(f[n][1]\)，说明股票还没卖出，不构成最终合法收益
  • 合法答案只能来自：
    • 空仓且可买 \(f[n][0]\)
    • 空仓但在冷冻期 \(f[n][2]\)

因此最终答案为： \[ \boxed{ \max\left( f[n][0],\; f[n][2] \right) } \]

六、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    static const int maxn = 5e3 + 5, neg = 0xcfcfcfcf;
    int maxProfit(vector<int>& prices) {
        int f[maxn][3], n = prices.size();
        f[0][0] = 0, f[0][2] = f[0][1] = neg;
        for (int i = 1; i <= n; ++i) {
            f[i][0] = max(f[i - 1][0], f[i - 1][2]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i - 1]);
            f[i][2] = f[i - 1][1] + prices[i - 1];
        }
        return max(f[n][0], f[n][2]);
    }
};

当然也可以用三个变量替代即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    static const int maxn = 5e3 + 5, neg = 0xcfcfcfcf;
    int maxProfit(vector<int>& prices) {
        int n = prices.size(), x = 0, y = neg, z = neg;
        for (int i = 1, tx, ty, tz; i <= n; ++i) {
            tx = max(x, z);
            ty = max(y, x - prices[i - 1]);
            tz = y + prices[i - 1];
            x = tx, y = ty, z = tz;
        }
        return max(x, z);
    }
};