跳至主要內容

买卖股票含手续费——状态机DP的通用框架

老张2026/4/30大约 6 分钟

买卖股票含手续费——状态机DP的通用框架

适读人群：Java后端工程师、股票系列DP学习者 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

股票买卖系列是LeetCode上最经典的DP系列之一，从最简单的只买一次（LeetCode 121），到无限次（122），到含冷冻期（309），到含手续费（714），再到最多k次（188），五六道题构成了一个完整的问题族。

我当时做这个系列的时候，每道题都单独推导，做到第三道就感觉大脑开始打结。后来我看到了一个"状态机DP通用框架"的思路，立刻豁然开朗：把"持仓状态"建模成状态机，所有股票题都用同一个框架，只是状态和转移条件不同。

714（含手续费）和122（无限次，不含手续费）是这个框架最清晰的展示。今天以714为主线，把状态机DP的框架讲透，然后横向对比整个股票系列。

一、题目解析

题号：LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee

题目描述：给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

示例：

  • 输入：prices = [1,3,2,8,4,9]，fee = 2，输出：8

二、状态机DP框架

2.1 建立状态机

每一天，我们处于以下状态之一：

  • 状态0：不持有股票（cash）
  • 状态1：持有股票（hold）

每个状态下，明天可以进行的操作：

当前状态操作明天状态收益变化
不持有买入持有-prices[i]
不持有不操作不持有0
持有卖出+手续费不持有+prices[i]-fee
持有不操作持有0

2.2 状态定义

定义 cash[i] = 第 i 天结束时，不持有股票的最大收益

定义 hold[i] = 第 i 天结束时，持有股票的最大收益

2.3 状态转移方程

cash[i] = max(cash[i-1],          // 今天不操作（昨天也不持有）
              hold[i-1] + prices[i] - fee)  // 今天卖出（昨天持有）

hold[i] = max(hold[i-1],           // 今天不操作（昨天也持有）
              cash[i-1] - prices[i])        // 今天买入（昨天不持有）

2.4 Mermaid状态机图

2.5 边界条件

  • cash[0] = 0：第0天不持有，收益为0
  • hold[0] = -prices[0]：第0天买入，收益为 -prices[0]

最终答案是 cash[n-1]（最后一天不持有才能锁定收益）。

三、解法一：标准状态机DP

public class BestTimeToBuyAndSellWithFee {
    
    /**
     * 714. 买卖股票含手续费 - 状态机DP
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)，可优化到O(1)
     */
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[] cash = new int[n];  // 不持有状态的最大收益
        int[] hold = new int[n];  // 持有状态的最大收益
        
        cash[0] = 0;
        hold[0] = -prices[0];  // 第0天买入
        
        for (int i = 1; i < n; i++) {
            // 不持有：昨天不持有不操作，或昨天持有今天卖出
            cash[i] = Math.max(cash[i - 1], hold[i - 1] + prices[i] - fee);
            // 持有：昨天持有不操作，或昨天不持有今天买入
            hold[i] = Math.max(hold[i - 1], cash[i - 1] - prices[i]);
        }
        
        return cash[n - 1];
    }
}

四、解法二：空间优化（O(1)）

因为每天的状态只依赖前一天，可以用两个变量替代数组：

/**
 * 714. 买卖股票含手续费 - 空间优化
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
public int maxProfitOptimized(int[] prices, int fee) {
    int cash = 0;              // 不持有的最大收益
    int hold = -prices[0];     // 持有的最大收益（第0天买入）
    
    for (int i = 1; i < prices.length; i++) {
        int prevCash = cash;
        // 不持有：不动 or 卖出
        cash = Math.max(cash, hold + prices[i] - fee);
        // 持有：不动 or 买入
        hold = Math.max(hold, prevCash - prices[i]);
        // 注意：用prevCash而非cash，避免同一天内买又卖
    }
    
    return cash;
}

注意：更新 hold 时要用 prevCash（上一天的不持有收益），不能用当天已更新的 cash，否则可能"当天卖出后当天再买入"，违反了"同一时间只能持有一只股票"的约束。

五、股票系列状态机对比

用同一个状态机框架，可以统一解决所有股票题：

题目限制状态转移特点
121（最多1次）k=1cash, holdhold只能从初始状态-price转来
122（无限次）k=∞cash, hold无手续费版本
309（冷冻期）k=∞，卖后冷冻1天cash, hold, cooldown多一个冷冻期状态
714（手续费）k=∞，手续费feecash, hold卖出时减fee
188（最多k次）k=kdp[k][2]三维变二维

122（无限次，无手续费）的转移：

cash[i] = max(cash[i-1], hold[i-1] + prices[i])  // 无手续费
hold[i] = max(hold[i-1], cash[i-1] - prices[i])

714 = 122 + 一个 fee 的差别。

309（冷冻期）的状态机：

六、举一反三

股票系列全集：

  1. LeetCode 121：最多买卖1次，直接贪心或DP均可
  2. LeetCode 122：无限次，贪心（每天涨就卖）或DP
  3. LeetCode 123：最多2次，188的特例（k=2）
  4. LeetCode 188：最多k次，三维DP压缩到二维
  5. LeetCode 309：冷冻期，多一个状态
  6. LeetCode 714：手续费，标准状态机

七、踩坑实录

坑一：更新hold时用了本轮更新后的cash

在O(1)空间优化版本里，必须先保存 prevCash 再更新 cash，最后用 prevCash 更新 hold。如果不保存，用已经更新的 cash 计算 hold，等于允许当天卖出当天再买入，这在"同一天只能持有一只"的约束下是不允许的（虽然122里结果恰好相同，但从语义上是错的）。

坑二：手续费加在买入还是卖出

fee可以在买入时扣，也可以在卖出时扣，两种都正确，只要一致就行。题目里一般约定在卖出时扣，所以 hold[i] = cash[i-1] - prices[i]（不扣fee），cash[i] = hold[i-1] + prices[i] - fee（卖出时扣fee）。

坑三：忘记处理只有1天的情况

如果 prices 长度为1，根本没法买卖，答案是0。有人的代码在长度1时会越界或返回负数。要么特判，要么保证初始值正确（cash=0，最后返回cash不会是负的）。

八、总结

买卖股票含手续费是状态机DP的最好入门案例。核心框架：

  • 状态：持仓（hold）和空仓（cash）
  • 每天的转移：在两种状态之间切换，取最大收益
  • 手续费：在卖出时扣除

掌握了这个状态机框架，整个股票系列都能用统一的视角来理解，不需要对每道题单独想思路。

编辑此页
最近更新:
贡献者: xiaozhangge