股票系列

本章目标：用统一的状态机 DP 模型解决 LeetCode 股票系列全部题目。

你将学到

• 股票问题的状态机模型
• "持有/不持有"状态设计
• 交易次数限制处理
• 冷冻期与手续费的处理
• 统一框架的推导过程

1. 概念

LeetCode 股票系列是经典的动态规划题目集，包括 LeetCode 121、122、123、188、309、714 等。虽然每道题看起来不同，但可以用统一的状态机模型解决。

通用状态定义：

dp[i][k][0] = 第 i 天结束时，最多交易 k 次，手上没有股票的最大利润
dp[i][k][1] = 第 i 天结束时，最多交易 k 次，手上有股票的最大利润

通用转移方程：

dp[i][k][0] = max(dp[i-1][k][0],          # 今天不操作
                   dp[i-1][k][1] + prices[i])  # 今天卖出

dp[i][k][1] = max(dp[i-1][k][1],          # 今天不操作
                   dp[i-1][k-1][0] - prices[i])  # 今天买入（买入消耗一次交易额度）

不同题目的差异：

• 121（一次交易）：k = 1
• 122（无限次）：k = ∞，所以 k 不影响，去掉维度
• 123（最多两次）：k ∈
• 188（最多 K 次）：k ∈
• 309（冷冻期）：k = ∞，卖出后不能立即买入
• 714（手续费）：k = ∞，卖出时扣手续费

2. 逐题精讲

LeetCode 121 · 买卖股票的最佳时机（一次交易）

def maxProfit(prices):
    """只允许一次买入卖出"""
    if not prices:
        return 0
    minPrice = prices[0]
    maxProfit = 0
    for price in prices:
        minPrice = min(minPrice, price)
        maxProfit = max(maxProfit, price - minPrice)
    return maxProfit

LeetCode 122 · 买卖股票的最佳时机 II（无限次）

def maxProfit(prices):
    """贪心：收集所有上涨段"""
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

DP 写法：

def maxProfit(prices):
    if not prices:
        return 0
    n = len(prices)
    # dp0 = 没股票，dp1 = 有股票
    dp0, dp1 = 0, -prices[0]
    for i in range(1, n):
        new_dp0 = max(dp0, dp1 + prices[i])
        new_dp1 = max(dp1, dp0 - prices[i])
        dp0, dp1 = new_dp0, new_dp1
    return dp0

LeetCode 123 · 最多两次交易

def maxProfit(prices):
    """
    四个状态：
    buy1: 第一次买入后的最大利润
    sell1: 第一次卖出后的最大利润
    buy2: 第二次买入后的最大利润
    sell2: 第二次卖出后的最大利润
    """
    buy1, sell1 = float('-inf'), 0
    buy2, sell2 = float('-inf'), 0
    for price in prices:
        buy1 = max(buy1, -price)         # 第一次买
        sell1 = max(sell1, buy1 + price) # 第一次卖
        buy2 = max(buy2, sell1 - price)  # 第二次买
        sell2 = max(sell2, buy2 + price) # 第二次卖
    return sell2

LeetCode 188 · 最多 K 次交易

def maxProfit(k, prices):
    if not prices or k == 0:
        return 0
    n = len(prices)
    # k > n/2 时等价于无限次交易
    if k > n // 2:
        profit = 0
        for i in range(1, n):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit

    # dp[k+1][2]
    dp = [[[0, 0] for _ in range(k + 1)] for _ in range(n)]
    for j in range(1, k + 1):
        dp[0][j][1] = -prices[0]
    for i in range(1, n):
        for j in range(1, k + 1):
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
    return dp[n-1][k][0]

LeetCode 309 · 含冷冻期

def maxProfit(prices):
    """
    三个状态：
    hold: 持有股票
    sold: 刚卖出（处于冷冻期）
    rest: 不持有且不在冷冻期
    """
    if not prices:
        return 0
    hold, sold, rest = -prices[0], 0, 0
    for i in range(1, len(prices)):
        prev_hold = hold
        hold = max(hold, rest - prices[i])  # 继续持有 或 从 rest 买入
        rest = max(rest, sold)               # 继续休息 或 从冷冻期出来
        sold = prev_hold + prices[i]         # 从持有状态卖出
    return max(sold, rest)

LeetCode 714 · 含手续费

def maxProfit(prices, fee):
    """卖出时扣手续费"""
    if not prices:
        return 0
    dp0, dp1 = 0, -prices[0]
    for i in range(1, len(prices)):
        new_dp0 = max(dp0, dp1 + prices[i] - fee)
        new_dp1 = max(dp1, dp0 - prices[i])
        dp0, dp1 = new_dp0, new_dp1
    return dp0

3. 复杂度

题目	时间	空间
121	O(n)	O(1)
122	O(n)	O(1)
123	O(n)	O(1)
188	O(nk)	O(nk) 或 O(k) 优化
309	O(n)	O(1)
714	O(n)	O(1)

4. 易错点

• ⚠️ 买入时消耗交易额度（k-1），卖出时不消耗
• ⚠️ 188 题 k 很大时（k > n/2）等价于无限次，否则会 MLE
• ⚠️ 冷冻期状态转移中 sold 必须用 prev_hold 计算，不能覆盖
• ⚠️ 初始状态 dp1 = -prices[0]（第一天买入），不是 0

5. 推荐刷题清单

题号	题名	难度	关键
121	买卖股票最佳时机	Easy	一次交易
122	买卖股票 II	Medium	无限次贪心
123	买卖股票 III	Hard	两次交易
188	买卖股票 IV	Hard	K 次交易
309	含冷冻期	Medium	三状态机
714	含手续费	Medium	卖出扣费

延伸阅读

• LeetCode 官方
• 股票问题通用解法
• 《算法导论》(CLRS)