LeetCode 309中等状态机 DP
最佳买卖股票含冷冻期 图解题解
这道题到底在问什么
卖出股票后第二天不能买入，求最大利润。
- prices
- [1,2,3,0,2]
- 输出
- 3
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合状态机 DP。
- 4hold 表示手里有股票hold[t]＝第 t 天结束时「手里持有股票」的最大利润（买入花了钱，所以常是负数或较小）。
- 5sold 表示今天刚卖出sold[t]＝第 t 天「今天刚把股票卖掉」后的利润。卖出当天单独成一态，是为了下一天强制冷冻。
- 6rest 表示空仓且不在刚卖出瞬间rest[t]＝第 t 天「空仓、且不在刚卖出那一瞬」的最大利润，也就是可以自由买入的状态。
- 7买入只能从 rest 转到 hold第 3 天 hold = max(昨 hold −1, 昨 rest 1 − price 0) = 1 —— 只能从「休息态 rest」花钱买入变成 hold。
- 8卖出从 hold 转到 sold第 4 天 sold = 昨 hold 1 + price 2 = 3 —— 把手里的股票卖掉，从 hold 转到 sold。
- 9冷冻期通过 sold 转 rest 表达第 3 天 rest = max(昨 rest 1, 昨 sold 2) = 2 —— 卖出后必须隔一天才能再买，冷冻期就靠「sold 只能转 rest」表达。
- 10每天滚动更新三个状态每天都用「昨天的三个值」同时算出今天的 hold / sold / rest —— 先把旧值存下来再更新，别互相覆盖。
- 11答案是 max(sold, rest)最后一天手里不该还留着股票，所以答案 = max(末日 sold 3, 末日 rest 2) = 3。
- 14把这句话记住，下次遇到同类题，就能更快选出方向。
- 19把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：卖出后第二天马上买入
✓ 对：买入只能从 rest 来，不能从 sold 来
这就是冷冻期的限制
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def maxProfit(self, prices):
hold, sold, rest = -10**9, 0, 0
for p in prices:
old_hold, old_sold, old_rest = hold, sold, rest
hold = max(old_hold, old_rest - p)
sold = old_hold + p
rest = max(old_rest, old_sold)
return max(sold, rest)C++
class Solution {
public:
int maxProfit(vector<int>& prices) {
int hold = INT_MIN, sold = 0, rest = 0;
for (int p : prices) {
int oh = hold, os = sold, orr = rest;
hold = max(oh, orr - p);
sold = oh + p;
rest = max(orr, os);
}
return max(sold, rest);
}
};Java
class Solution {
public int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
for (int p : prices) {
int oh = hold, os = sold, orr = rest;
hold = Math.max(oh, orr - p);
sold = oh + p;
rest = Math.max(orr, os);
}
return Math.max(sold, rest);
}
}套路模板 · 状态机 DP
# 状态机 DP 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界class Solution {
public:
int maxProfit(vector<int>& prices) {
int hold = INT_MIN, sold = 0, rest = 0;
for (int p : prices) {
int oh = hold, os = sold, orr = rest;
hold = max(oh, orr - p);
sold = oh + p;
rest = max(orr, os);
}
return max(sold, rest);
}
};class Solution {
public int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
for (int p : prices) {
int oh = hold, os = sold, orr = rest;
hold = Math.max(oh, orr - p);
sold = oh + p;
rest = Math.max(orr, os);
}
return Math.max(sold, rest);
}
}复杂度
时间复杂度
O(n)
每个核心状态按算法要求处理固定次数
空间复杂度
O(1)
只保存必要的辅助结构或递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最佳买卖股票含冷冻期 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用状态机 DP？+
每天决策依赖昨天处于哪种状态(持有/冷冻/可买)；用几个状态变量表示，转移清晰、O(n)。
和普通买卖(LC122)差在哪？+
多了「卖出后冷冻一天」的约束，所以多一个冷冻状态、买入来源受限。
复杂度？+
O(n) 时间、O(1) 空间(几个状态变量滚动)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。