cswork / 模板打开 500 路题单

第 29 站 · 动态规划

股票交易状态机

持有 / 冷却 / 空仓三状态 时间 O(n) · 空间 O(1)

打开 500 路题单 · 第 29 站 · 6 题
先学
学完去
没有后续站依赖它。
面试频次
7 家公司考过 · 面经出现 9 次Coinbase 2、Meta 2、Citadel 1、Flipster 1、Point72 1

先做这道

LC 121买卖股票的最佳时机简单
卡住再看

维护历史最低买入价，明确必须先买后卖且允许不交易。

要点

  1. 先写清楚每天结束时可能处于哪几种状态，再写「昨天的哪种状态 + 今天的什么动作」能到达它。
  2. 同一天的几个新值都要用前一天的旧值计算，所以要同时赋值或者先存临时变量。
  3. 最多 k 次交易就加一维 k；手续费在每次卖出（或买入）时扣一次；只交易一次就是「记录历史最低价」。

易错点

  • 持有状态初始化成 0，相当于第 0 天白送了一股。
  • 用负无穷做初值时，C++ / Java 里 hold + p 会溢出；取 MIN / 2 这样的值。
  • 有冷却期时，买入只能从「空仓」状态转过来，不能从「刚卖出」状态直接买。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

状态机 DP · 含冷冻期的股票买卖

价格 1, 2, 3, 0, 2，卖出后要冷冻一天，最大利润是多少？

换个输入
价格
1第 0 天
2第 1 天
3第 2 天
0第 3 天
2第 4 天
持有
·持有[0]
·持有[1]
·持有[2]
·持有[3]
·持有[4]
冷冻
·冷冻[0]
·冷冻[1]
·冷冻[2]
·冷冻[3]
·冷冻[4]
空仓
·空仓[0]
·空仓[1]
·空仓[2]
·空仓[3]
·空仓[4]
当前处理已发现 / 已计算答案
第几天
—
最大利润
0

每天结束时处在三种状态之一：持有股票、刚卖出（明天冷冻不能买）、空仓可买。每列只由前一列算出。

始终成立每天的三个状态只由前一天的三个状态转移而来：hold → cool（卖），free → hold（买），cool → free（等一天）。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 121。

Python
def max_profit_cooldown(prices: list[int]) -> int:
    """Unlimited trades, but after selling you must wait one day before buying."""
    hold, cool, free = float("-inf"), 0, 0  # profit at the end of a day in each state
    for p in prices:
        hold, cool, free = (
            max(hold, free - p),  # keep holding, or buy today (only from free)
            hold + p,  # sell today
            max(free, cool),  # rest
        )
    return max(cool, free)
C++
// Unlimited trades, but after selling you must wait one day before buying.
long long maxProfitCooldown(const vector<int>& prices) {
    long long hold = LLONG_MIN / 2, cool = 0, free = 0;  // profit at day end in each state
    for (int p : prices) {
        long long h = max(hold, free - p);  // keep holding, or buy today (only from free)
        long long c = hold + p;             // sell today
        long long f = max(free, cool);      // rest
        hold = h, cool = c, free = f;
    }
    return max(cool, free);
}
Java
class Solution {
    // Unlimited trades, but after selling you must wait one day before buying.
    long maxProfitCooldown(int[] prices) {
        long hold = Long.MIN_VALUE / 2, cool = 0, free = 0; // profit at day end in each state
        for (int p : prices) {
            long h = Math.max(hold, free - p); // keep holding, or buy today (only from free)
            long c = hold + p; // sell today
            long f = Math.max(free, cool); // rest
            hold = h;
            cool = c;
            free = f;
        }
        return Math.max(cool, free);
    }
}
Go
import "math"

// maxProfitCooldown allows unlimited trades, but after selling you must wait
// one day before buying again.
func maxProfitCooldown(prices []int) int {
	hold, cool, free := math.MinInt/2, 0, 0 // profit at the end of a day in each state
	for _, p := range prices {
		// keep holding or buy today (only from free); sell today; rest
		hold, cool, free = max(hold, free-p), hold+p, max(free, cool)
	}
	return max(cool, free)
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

最多 k 笔交易：buy[j] / sell[j] 两组状态时间 O(n × k) · 空间 O(k)

交易次数有上限（最多 2 笔、最多 k 笔）时，状态按「第几笔」展开：buy[j] 是第 j 笔买入后手上的最好余额，sell[j] 是做完 j 笔后的最好余额，每天按 j 从小到大更新一遍。LC 188 买卖股票的最佳时机 IV，LC 123 是 k = 2。

Python
def max_profit_k(k: int, prices: list[int]) -> int:
    """Best profit with at most k buy-sell pairs, holding one share at a time (LC 188)."""
    buy = [float("-inf")] * (k + 1)  # buy[j]: best balance while holding in trade j
    sell = [0] * (k + 1)  # sell[j]: best balance after completing j trades
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)  # buy today, opening trade j
            sell[j] = max(sell[j], buy[j] + p)  # sell today, closing trade j
    return sell[k]
C++
// Best profit with at most k buy-sell pairs, holding one share at a time (LC 188).
int maxProfitK(int k, const vector<int>& prices) {
    vector<int> buy(k + 1, INT_MIN / 2), sell(k + 1, 0);  // holding in trade j / after completing j trades
    for (int p : prices)
        for (int j = 1; j <= k; j++) {
            buy[j] = max(buy[j], sell[j - 1] - p);  // buy today, opening trade j
            sell[j] = max(sell[j], buy[j] + p);  // sell today, closing trade j
        }
    return sell[k];
}
Java
class Solution {
    // Best profit with at most k buy-sell pairs, holding one share at a time (LC 188).
    int maxProfitK(int k, int[] prices) {
        int[] buy = new int[k + 1], sell = new int[k + 1]; // holding in trade j / after completing j trades
        Arrays.fill(buy, Integer.MIN_VALUE / 2);
        for (int p : prices)
            for (int j = 1; j <= k; j++) {
                buy[j] = Math.max(buy[j], sell[j - 1] - p); // buy today, opening trade j
                sell[j] = Math.max(sell[j], buy[j] + p); // sell today, closing trade j
            }
        return sell[k];
    }
}
Go
// maxProfitK returns the best profit with at most k buy-sell pairs, one share at a time (LC 188).
func maxProfitK(k int, prices []int) int {
	buy, sell := make([]int, k+1), make([]int, k+1) // holding in trade j / after completing j trades
	for j := range buy {
		buy[j] = -1 << 60
	}
	for _, p := range prices {
		for j := 1; j <= k; j++ {
			buy[j] = max(buy[j], sell[j-1]-p) // buy today, opening trade j
			sell[j] = max(sell[j], buy[j]+p)  // sell today, closing trade j
		}
	}
	return sell[k]
}
手续费：持有 / 空仓两个状态时间 O(n) · 空间 O(1)

不限次数、只是每笔多一个手续费（或者每次卖出后什么限制都没有）时，两个状态就够：hold 是手上有股票的最好余额，free 是空仓的最好余额；卖出时扣掉手续费。LC 714 买卖股票的最佳时机含手续费；LC 122 是手续费为 0。

Python
def max_profit_fee(prices: list[int], fee: int) -> int:
    """Unlimited trades, each sale paying fee (LC 714)."""
    hold, free = -prices[0], 0  # best balance holding a share / holding none
    for p in prices[1:]:
        hold, free = max(hold, free - p), max(free, hold + p - fee)  # both from yesterday's values
    return free
C++
// Unlimited trades, each sale paying fee (LC 714).
int maxProfitFee(const vector<int>& prices, int fee) {
    int hold = -prices[0], free = 0;  // best balance holding a share / holding none
    for (size_t i = 1; i < prices.size(); i++) {
        int p = prices[i], held = hold;  // both updates read yesterday's values
        hold = max(hold, free - p);
        free = max(free, held + p - fee);
    }
    return free;
}
Java
class Solution {
    // Unlimited trades, each sale paying fee (LC 714).
    int maxProfitFee(int[] prices, int fee) {
        int hold = -prices[0], free = 0; // best balance holding a share / holding none
        for (int i = 1; i < prices.length; i++) {
            int p = prices[i], held = hold; // both updates read yesterday's values
            hold = Math.max(hold, free - p);
            free = Math.max(free, held + p - fee);
        }
        return free;
    }
}
Go
// maxProfitFee returns the best profit with unlimited trades, each sale paying fee (LC 714).
func maxProfitFee(prices []int, fee int) int {
	hold, free := -prices[0], 0 // best balance holding a share / holding none
	for _, p := range prices[1:] {
		hold, free = max(hold, free-p), max(free, hold+p-fee) // both from yesterday's values
	}
	return free
}

为什么对

  1. 每天结束时只可能处于有限几种状态（持股、刚卖出在冷冻期、空仓可买）。列出每种状态由昨天哪种状态、经过今天什么动作到达，就覆盖了所有交易序列。
  2. 冷冻期的约束体现在「买入只能从空仓状态转移」：卖出当天进入冷冻态，第二天只能转成空仓，不能直接买。
  3. 今天的三个值都必须由昨天的值算出，要同时赋值或用临时变量；否则同一天先卖后买会被错误地算进去。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文
股票题我画状态机：每天结束时可能持股、刚卖出处于冷冻期，或者空仓可以买。然后写出每个状态由昨天哪个状态、今天做了什么转移过来，比如持股等于昨天就持股和昨天空仓今天买入两者取大。今天的值都要从昨天的值算，所以同时赋值。最多 k 笔交易就加一维 k，手续费在卖出时扣一次，O(n) 时间、O(1) 空间。
English
For stock problems I draw a state machine: at the end of a day I am holding, cooling down after a sale, or free to buy. Then I write each state from yesterday's states and today's action, for example holding is the better of holding already and buying today from free. All of today's values must come from yesterday's, so I assign them together. At most k trades adds a dimension for k, a fee is subtracted once per sale, and it all runs in O(n) time with O(1) space.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。 只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）
这道题你会了吗？

小测

3 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。 去 OA 选择题练习

3 道题
  1. 股价依次是 [6, 2, 9, 1, 4, 8]，可以买卖任意多次，但手里最多持有一股（卖出后才能再买）。最大利润是？
  2. 「最多交易 k 次」的股票问题，n 天价格。当 k ≥ n / 2 时可以怎么处理？
  3. n = len(prices)，最多交易 k 次。时间和额外空间分别是？
    def max_profit(k, prices):
    buy = [float('-inf')] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for t in range(1, k + 1):
            buy[t] = max(buy[t], sell[t - 1] - p)
            sell[t] = max(sell[t], buy[t] + p)
    return sell[k]

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

分档练习

本站在 500 路里的 6 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 1

#题目一句话思路难度分
121买卖股票的最佳时机维护历史最低买入价，明确必须先买后卖且允许不交易。

核心 3

#题目一句话思路难度分
122买卖股票的最佳时机 II用持有和未持有状态描述多次交易，并解释累加正收益的等价性。
714买卖股票的最佳时机含手续费在一次交易中只扣一次手续费，检查原地更新是否改变状态语义。
309买卖股票的最佳时机含冷冻期将冷冻期显式建模，说明昨天卖出为何不能直接转入今天买入。

进阶 2

#题目一句话思路难度分
123买卖股票的最佳时机 III给状态增加交易次数，区分第一次和第二次持仓的资金来源。
188买卖股票的最佳时机 IV推广到任意交易上限，处理k很大时的退化情况与复杂度优化。

本站 OA 真题 2

全部 2 道