前言

LeetCode 309 是股票买卖系列里状态最多的一题：允许多次买卖，但卖出股票的第二天不能买入，也就是有一天的冷冻期。求能获得的最大利润。题目通常给出一个整数数组prices，prices[i]表示第i天的股价。

这题的难点不在代码长度，而在状态定义：持有股票、当天卖出、冷冻期、正常不持有，这几种状态之间的转移容易混淆。常见的错误包括：把“卖出后第二天不能买”写成“卖出当天不能买”；用sold[0] = 0初始化，凭空得到一笔卖出收益；把买入的来源写成前一天卖出，导致冷冻期被跳过；最后返回持有股票的状态；以及滚动变量更新时用已覆盖的旧值计算新值。

本文以 C++17 为准，用三个状态建立动态规划：hold（持有股票）、sold（当天刚卖出）、rest（不持有且不在冷冻期）。先写二维版本说明转移，再压缩成常数空间。所有推导都是按状态定义手工进行的，不涉及运行结果。

一、状态定义

把第i天结束时的状态分为三类：

这里的“现金”只计算交易带来的盈亏，初始为 0。买入时减去股价，卖出时加上股价。

为什么需要sold和rest两个“不持有”状态？因为冷冻期的限制只作用于“刚卖出的下一天”。如果把所有不持有状态合并成一个，就无法区分“昨天刚卖，今天不能买”和“已经空仓一段时间，今天可以买”。

状态转移：

1. 
   
2. 持有：要么昨天就持有，今天不动；要么今天买入。今天能买入的前提是昨天处于rest（不持有且不在冷冻期）。所以
3. 
   

hold[i] = max(hold[i-1], rest[i-1] - prices[i])。

1. 
   
2. 当天卖出：昨天必须持有，今天按prices[i]卖出：
3. 
   

sold[i] = hold[i-1] + prices[i]。

1. 
   
2. 空仓休息：要么昨天就已经在休息，要么昨天刚卖出，今天进入冷冻期：
3. 
   

rest[i] = max(rest[i-1], sold[i-1])。

注意hold的买入来源是rest[i-1]，不是sold[i-1]。如果第i-1天卖出，第i天是冷冻期，不能买入；而rest[i]的转移允许sold[i-1]进入休息状态，到第i+1天才能从rest[i]买入。这正是“卖后隔一天才能买”的体现。

二、初始化与答案

第 0 天：

• 
  
• 买入：hold[0] = -prices[0]；
• 
  
• 卖出：第 0 天不可能卖出（没有前一天持仓），应设为负无穷；
• 
  
• 休息：rest[0] = 0，表示什么都没做。
• 
  

sold[0]不能设为 0。设为 0 相当于“第 0 天无成本卖出得到 0 元”，后续可能被错误地当成有效收益，甚至让答案虚高。用INT_MIN或足够小的负数表示不可达。

最终答案是max(sold[n-1], rest[n-1])，不能是hold[n-1]。最后一天还持有股票，说明没有卖出，收益尚未兑现；题目要求的是完成交易后的最大利润。sold和rest都表示不持有，取两者较大值即可。

若prices为空，利润为 0；若只有一个元素，无法完成一次买卖，利润也是 0。这两种情况要在代码入口处理。

三、二维 DP 写法

先写出完整表格版本，便于核对状态：

// 适用于 C++17
#include <algorithm>
#include <limits>
#include <vector>

int max_profit_2d(const std::vector<int>& prices)
{
const int n = static_cast<int>(prices.size());
if (n < 2)
return 0;

const long long NEG = std::numeric_limits<long long>::min() / 2;

std::vector<long long> hold(n, NEG);
std::vector<long long> sold(n, NEG);
std::vector<long long> rest(n, 0);

hold[0] = -prices[0];

for (int i = 1; i < n; ++i)
{
hold[i] = std::max(hold[i - 1], rest[i - 1] - prices[i]);
sold[i] = hold[i - 1] + prices[i];
rest[i] = std::max(rest[i - 1], sold[i - 1]);
}

return static_cast<int>(std::max(sold[n - 1], rest[n - 1]));
}

NEG取long long最小值的一半，是为了在sold[i] = hold[i-1] + prices[i]中避免溢出。实际上hold[i-1]从第 1 天起就已是有效值（要么是-prices[0]，要么是买入后的现金），不会用到NEG；但保留这个保护不影响正确性。

用题目常见的例子prices = [1, 2, 3, 0, 2]手工推演：

第 4 天结束时，sold = 3、rest = 2，答案是 3。交易过程可以是第 0 天买、第 2 天卖（赚 2），冷冻第 3 天，第 3 天买、第 4 天卖（赚 2），总利润 4？这里要小心：第 2 天卖出后，第 3 天是冷冻期，不能买入。因此上面的 3 对应的交易是第 0 天买、第 1 天卖（赚 1），第 2 天买、第 4 天卖？第 2 天卖出后第 3 天冷冻，不能第 2 天买。让我按状态回溯：第 4 天sold = hold[3] + 2 = 1 + 2 = 3，hold[3] = 1来自rest[2] - 0 = 1 - 0 = 1，即第 2 天休息后第 3 天以 0 买入；rest[2] = 1来自sold[1] = 1，即第 1 天卖出。第 1 天的卖出来自第 0 天买入：-1 + 2 = 1。所以交易是：第 0 天买、第 1 天卖（+1）；第 2 天冷冻；第 3 天买、第 4 天卖（+2）；总计 3。正确。第 2 天卖出再第 3 天买是违反冷冻期的，手工推演时正好能暴露这种错误理解。

这个例子说明：冷冻期是“卖出后的下一个交易日”，不是“卖出当天”。第 1 天卖出，第 2 天不能买；第 2 天休息，第 3 天才能买。

四、滚动变量：常数空间

二维表只依赖前一天，因此可以用三个变量滚动：

// 适用于 C++17
#include <algorithm>
#include <limits>
#include <vector>

int max_profit(const std::vector<int>& prices)
{
if (prices.size() < 2)
return 0;

const long long NEG = std::numeric_limits<long long>::min() / 2;

long long hold = -prices[0];
long long sold = NEG;
long long rest = 0;

for (std::size_t i = 1; i < prices.size(); ++i)
{
const long long price = prices[i];

const long long next_hold = std::max(hold, rest - price);
const long long next_sold = hold + price;
const long long next_rest = std::max(rest, sold);

hold = next_hold;
sold = next_sold;
rest = next_rest;
}

return static_cast<int>(std::max(sold, rest));
}

三个next_临时变量必须全部算完再统一赋值。如果写成：

hold = std::max(hold, rest - price);
sold = hold + price; // 错误：hold 已被更新
rest = std::max(rest, sold); // 错误：sold 已被更新

那么sold会用到“今天已经买入后的 hold”，相当于同一天既买又卖，rest也会用到今天的sold，冷冻期被压缩。这类错误在滚动数组里很常见，根源是没有区分“前一天的状态”和“今天的状态”。

时间复杂度和空间复杂度都是O(n)时间和O(1)额外空间（不计输入）。

五、另一种等价写法

也可以用两个数组hold和cash，其中cash[i]表示第i天结束时不持有股票的现金，买入时要求从前两天的不持有状态转移：

// 适用于 C++17
int max_profit_alt(const std::vector<int>& prices)
{
const int n = static_cast<int>(prices.size());
if (n < 2)
return 0;

std::vector<int> hold(n, 0);
std::vector<int> cash(n, 0);

hold[0] = -prices[0];
cash[0] = 0;

for (int i = 1; i < n; ++i)
{
hold[i] = std::max(hold[i - 1], (i >= 2 ? cash[i - 2] : 0) - prices[i]);
cash[i] = std::max(cash[i - 1], hold[i - 1] + prices[i]);
}

return cash[n - 1];
}

这里cash[i-2]的含义是：如果第i-1天卖出，第i天处于冷冻期，不能用cash[i-1]买入；只能用第i-2天结束时的现金。i < 2时，第 0 天或第 1 天买入都不受冷冻期限制，用初始现金 0。

两种写法等价，但三状态版本把“冷冻期”显式建模，转移条件的含义更直观；两状态版本更短，但i >= 2的下标容易写错。面试或刷题时选一种自己能手推清楚的即可，不要在两种记法之间来回切换。

六、边界与变体

需要检查的边界：

• 
  
• prices为空：返回 0，不能访问prices[0]；
• 
  
• 只有一个价格：无法完成买卖，返回 0；
• 
  
• 价格全部下跌：最优是不交易，答案为 0；
• 
  
• 价格全部相同：不交易，答案为 0；
• 
  
• 冷冻期跨过数组末尾：最后一天卖出后没有后续买入，答案仍按sold计算，不需要额外处理。
• 
  

股票系列题容易混淆变体：

把 309 的rest状态去掉、允许sold[i-1]直接买入，就退化成 122；在卖出时减去fee，就得到 714 的无冷冻期版本。理解状态机后，这些变体只是在转移式上增减项。

常见坑点

1. 
   
2. ❌ 把sold[0]初始化为 0。
3. 
   

✅ 第 0 天不可能卖出，应设为负无穷；否则会凭空产生收益，污染后续转移。

1. 
   
2. ❌ 买入来源写成sold[i-1] - prices[i]。
3. 
   

✅ 卖出后第二天不能买，买入只能来自rest[i-1]；sold[i-1]要到rest[i]才可用。

1. 
   
2. ❌ 把冷冻期理解为“卖出当天不能买”。
3. 
   

✅ 卖出当天本来就不能同时买；限制的是卖出后的下一个交易日，即第i天卖出，第i+1天不能买。

1. 
   
2. ❌ 最终返回hold[n-1]。
3. 
   

✅ 返回max(sold[n-1], rest[n-1])；持有股票意味着尚未卖出，利润没有兑现。

1. 
   
2. ❌ 滚动更新时先改hold再算sold，用了今天的状态。
3. 
   

✅ 先把next_hold、next_sold、next_rest都算出来，再统一赋值。

1. 
   
2. ❌ 用int存负无穷并直接加价格，导致溢出。
3. 
   

✅ 用足够小的负数（如INT_MIN / 2）或long long，避免加法溢出。

1. 
   
2. ❌ 忘记处理空数组或单元素数组，访问prices[0]越界。
3. 
   

✅ 入口处判断prices.size() < 2，直接返回 0。

1. 
   
2. ❌ 把 309 的转移直接套到 122（无冷冻期），答案偏小。
3. 
   

✅ 先确认题目约束；无冷冻期时卖出后可以立即买入，不需要rest的延迟。

总结

309 的关键是把“冷冻期”建模成一个独立状态，而不是在买入时临时判断。sold表示“今天刚卖，明天不能买”，rest表示“已经空仓，随时可买”；两者分开后，转移式自然满足“卖后隔一天”的约束。写完后用[1,2,3,0,2]这类包含下跌和反弹的例子手工推演一遍，重点检查买入来源和滚动变量的更新顺序，基本就能排除大多数错误。