LeetCode 714 这道题在股票买卖系列里卡过不少人的脖子。题目全名叫“买卖股票的最佳时机含手续费”给你一个 prices 数组代表未来 n 天的股价你可以不限次数买入卖出但每完成一笔完整的交易要交一笔固定的手续费 fee最后能留下的最大现金就是答案。我第一次做这题时下意识拿 122 题那套“见涨就卖”的贪心逻辑去套样例直接对不上后来把状态机 DP 的转移方程自己推了一遍才意识到手续费这个变量看似只加了一位实则把题目的结构从“局部差价”变成了“全局持仓收益”。这篇文章会从暴力思路讲起一步步推出“现金/持仓”两个状态的状态机解法解释为什么 122 的贪心在这里会失灵再给出一个能通吃 121、122、123、188、309、714 的框架。如果你正准备面试或者刷到中等难度题后卡在状态转移这篇应该能帮上忙如果你只是想抄一份能过的代码跳到第三节就可以。1. 题目到底要做什么先别急着写代码1.1 输入输出和限制条件先把题面吃透。输入是两个东西股价数组prices和手续费fee。输出是一个整数表示经过无限次交易后账户里现金的最大值。每次交易的定义是一买一卖手续费按次收不是按股数收。举个例子prices [1, 3, 2, 8, 4, 9]fee 2那么最优路径是第 0 天买入、第 3 天卖出赚到8 - 1 - 2 5再第 4 天买入、第 5 天卖出赚到9 - 4 - 2 3总利润 8。注意中间 1 到 3、3 到 8 这两段价差如果分开吃一共要做三次交易毛利是(3-1)(8-3)(9-4) 12扣掉三次手续费 6最后只剩 6反而亏了 2。这个简单例子已经能说明手续费会逼迫你放弃一些“看起来能赚”的短期差价。LeetCode 的约束是prices.length最大到 5 万价格和fee的数量级也在 1e5 以内。这意味着O(n^2)级别的算法基本不可行必须设计成一次遍历搞定的线性算法。这也是为什么状态机 DP 是标准解法空间O(1)时间O(n)扫一遍数组就能出答案。1.2 暴力枚举为什么不可行不熟悉的读者可能会想每天无非三个选择——买入、卖出、不动那我枚举所有指令序列不就行了问题是 n 天会产生 3 的 n 次方种可能50 天就已经是天文数字5 万天根本没法碰。另一类思路是枚举“买入日”和“卖出日”的组合把所有可能交易段算出来再选一段不重叠的最优组合这种做法的复杂度也是O(n^2)5 万的数据规模下直接超时。所以正确答案必须在遍历过程中动态维护信息。每遍历到一天我们需要知道“今天结束时不持有股票的状态下最多有多少现金”以及“今天结束时还持有股票的状态下最多有多少现金”。这两个值一旦能从前一天递推过来问题就变成了一道标准的线性动态规划。这也是整个状态机思路最核心的出发点。1.3 直觉陷阱每个上涨都吃没有手续费时也就是 LeetCode 122大家会背一个口诀只要今天的价格比昨天高就把差价累加。因为交易零成本每一段上涨都独立成立把所有正差价加在一起就是最大利润。手续费一进来这个“每段独立”的假设立刻被打破——一次短线交易的净利润是卖出价 - 买入价 - fee只有差价能覆盖掉 fee 才值得做。如果两个小波段的差价加起来还不如一次长持有的差价那最优策略一定不是“每个上涨都吃”而是“合并成一个大波段”。用刚才的例子再感受一下1 到 3 吃一次3 到 8 吃一次2 到 9 再吃一次交易次数多、手续费多总利润反而低。最优路线是 1 直接拿到 84 再拿到 9只做两笔。手续费本质上给每次交易设了一个“最低盈利门槛”破坏了局部贪心的成立条件。理解这一点后面看 DP 的状态转移就顺理成章了。2. 状态机DP为什么“手里有没有股票”这个维度就够了2.1 状态设计的直觉做 DP 第一步永远是问自己题目需要记录什么信息才能做出后续决策对于这道题核心信息只有一个——你现在手里有没有股票。为什么够用因为当你站在第 i 天考虑是否买入时你不需要知道之前做了多少笔交易也不关心成本具体摊在哪一天只要知道“如果不买我手里最多有多少现金如果买我要花掉多少钱然后进入持仓状态”。反过来当你考虑是否卖出时也只需要知道“如果我现在还拿着股票它的价值是多少”。于是给出两个状态dp[i][0]第 i 天结束时不持有股票账上最多有多少现金。dp[i][1]第 i 天结束时持有股票账上最多有多少现金注意这里现金会是买入股票后的剩余值所以可能比不持有状态小甚至是个负数。为什么不需要第三个状态来表示“今天刚卖完”或者“今天是冷静期”因为 714 没有限制卖出后不能马上买入。所以任何历史信息都已经压缩在这两个状态里了。比起某些变种题需要“冷冻期”状态这题已经是非常舒服的两状态模型。2.2 状态转移的两条边从第i-1天到第i天每个状态有两条路可以走对于dp[i][0]第一昨天就不持有股票今天继续看着什么都不做继承dp[i-1][0]。第二昨天持有股票今天卖出得到dp[i-1][1] prices[i] - fee这里减掉手续费代表这笔交易正式结算。两者取最大值。对于dp[i][1]第一昨天就持有股票今天继续拿住继承dp[i-1][1]。第二昨天不持有股票今天买入现金变成dp[i-1][0] - prices[i]进入持仓状态。两者取最大值。如果把两个状态画成图就是两个节点之间来回切换的转移边。每一次切换都对应一次“买入”或“卖出”的实际动作不切换就是继续持有或继续空仓。状态机的优雅之处就在这里交易次数无限但状态只有两个因为所有“已经完成的路”都被当前持仓和当前现金概括掉了。2.3 手续费放在卖出那一步的原因手续费在数学上放在买入端还是卖出端结果完全等价只要你只扣一次。我推荐放在卖出端也就是dp[i-1][1] prices[i] - fee这一项。理由有三点第一符合直觉交易结算时才付手续费第二初始化简单第一天如果不买就是 0如果买就是-prices[0]不用额外把 fee 塞进去第三方便跟 122 题对比122 是无手续费版本把- fee删掉就是原来的代码改动一目了然。也有题解把手续费放在买入时即初始化hold -prices[0] - fee买入时再扣一次。两种写法最终答案一样但容易犯的错是“两边都扣”——买入时扣完卖出时又扣这样每笔交易交了两次手续费结果必然偏小。我自己的习惯是固定在卖出端少一个思考点面试讲起来也干净。3. 转移方程推导与代码落地别急着背别人的代码3.1 从第 i-1 天到第 i 天的严格递推把上一节的语言描述写成数学表达式dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i] - fee) dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])这里有个隐秘但重要的点dp[i]的两个值都只依赖dp[i-1]的旧值不存在“今天先卖出再买入”这种同一天循环操作的路径。因为如果允许同一天先卖出再买入就相当于多支付了一次手续费而净持仓没有变化这种操作永远不可能比继续持有更优所以即便你写出了一条这样的转移路径max也会自动把它淘汰掉。理解这一点之后空间优化时就不会被“新旧值会不会串位”困扰。时间复杂度是O(n)空间复杂度如果开二维数组是O(n)。但既然每一天只依赖前一天二维数组里 90% 的信息都冗余了。3.2 初始化与遍历细节初始化很直接第 0 天结束时如果不持有股票那现金就是 0所以dp[0][0] 0如果持有股票说明第一天就买了现金是-prices[0]所以dp[0][1] -prices[0]。这里采用“卖出时扣手续费”的策略所以买入时不用管 fee。遍历从第 1 天开始到第n-1天结束。最终答案返回dp[n-1][0]——最后一天结束时手里应该没有股票因为你拿着股票没有卖出那部分浮动收益还没变成现金不能算进最终利润。这个细节看起来简单但我见过不少人最后返回max(dp[n-1][0], dp[n-1][1])虽然在这一题里通常不影响结果但逻辑上是讲不通的最好养成返回空仓状态的习惯。还要处理一个极端情况prices为空或者只有一个元素时没有任何交易能做直接返回 0。LeetCode 给的约束一般保证长度不小于 1但写防御性代码没坏处。3.3 一维空间优化的正确打开方式既然状态转移只依赖前一天用两个变量滚动即可cash代表当前天不持有股票的最大现金。hold代表当前天持有股票的最大现金。每次迭代时用旧的cash和hold同时算出新的两个值再整体更新。我见过很多题解直接这样写cash max(cash, hold price - fee) hold max(hold, cash - price)这属于“能用但思想不干净”的写法第二行里的cash可能已经包含了今天卖出的收入用这个新现金买入等于允许同一天先卖后买。前面说过由于多扣一次手续费max通常不会选这种路径所以多数样例能过。但在一些变种题里比如带冷冻期或者 K 次交易限制这个顺序错误就会实实在在造成 WAWrong Answer。我的建议是一律把旧值先存起来pre_cash, pre_hold cash, hold cash max(pre_cash, pre_hold price - fee) hold max(pre_hold, pre_cash - price)这样代码读起来也清楚——你明确告诉读者今天的决策只基于昨天结束时的状态。3.4 完整可运行的Python实现把上面的思路落到代码def maxProfit(prices, fee): if not prices: return 0 cash 0 # 不持有股票的最大现金 hold -prices[0] # 持有股票的最大现金 for i in range(1, len(prices)): pre_cash, pre_hold cash, hold cash max(pre_cash, pre_hold prices[i] - fee) hold max(pre_hold, pre_cash - prices[i]) return cash用prices [1, 3, 2, 8, 4, 9]fee 2手推一遍天数价格cashhold说明010-1初始化130-1卖出不划算继续持有220-1同日买不划算继续持有385-1卖出获利 54451用现金买入等效继续持仓5981再次卖出总利润 8第 4 天hold 1看着有点奇怪它的含义是如果第 4 天结束时还持有股票那相比空仓现金 5持有状态价值为 5 - 4 1。这其实是表示“第 3 天卖出获利后第 4 天又买回来继续等涨”的一条合法路径。这里很容易把自己绕晕记住一点状态值不是“账户里剩多少钱”而是“这个状态相比空仓多值多少钱”理解就顺畅了。Java 版本也顺便给一份面试常写public int maxProfit(int[] prices, int fee) { int cash 0; int hold -prices[0]; for (int i 1; i prices.length; i) { int preCash cash, preHold hold; cash Math.max(preCash, preHold prices[i] - fee); hold Math.max(preHold, preCash - prices[i]); } return cash; }4. 与122题对比手续费出现后贪心为什么失灵4.1 122题无手续费时的贪心逻辑122 题没有手续费常见的贪心解法是从左到右扫一遍只要prices[i] prices[i-1]就把差值加进答案。原因是交易成本为零我可以昨天买今天卖赚到的每一段价差都独立有效。最终结果等于把所有上涨片段全部吃到这在数学上等于“总涨幅的最大化分解”。举个例子prices [1, 3, 2, 8]122 的贪心会累加(3-1) (8-2) 8。这个操作可以解释成1 买 3 卖、2 买 8 卖。每段利润各自落袋。4.2 714为什么贪心会多扣手续费现在给同样的例子加上fee 2。如果还按 122 的贪心做两笔交易真实利润是(3-1-2) (8-2-2) 4。但最优解只要一笔1 买 8 卖利润8-1-2 5。差距达到 1正好是一次多余的手续费。问题的根源在于122 贪心认为“每一段上涨都值得独立收割”但 714 里每收割一次都要付一笔固定费用。两段小涨合在一起虽然放弃了中间那次卖出的价差但省下了一笔手续费。当省下的手续费大于中间价差时合并就更优。所以局部差价的贪心在手续费面前失效了必须在“卖与不卖”之间做权衡这正是 DP 状态机的用武之地。4.3 一种“变种贪心”的思路与DP的等价性力扣评论区偶尔能看到一种看起来不像 DP 的解法代码很简短def maxProfit(prices, fee): buy prices[0] fee profit 0 for p in prices[1:]: if p fee buy: buy p fee elif p buy: profit p - buy buy p return profit它维护的是一个“虚拟持仓成本”buy表示当前最优的买入成本且已经加上了手续费。当发现某个价格加手续费后比当前buy还低说明市场上出现了更便宜的买入点就更新buy当价格高于buy时说明卖出能赚到钱先把利润累加进profit然后把buy更新成当前价格相当于“卖掉后以当前价继续持有”等待后面更高的价格。这个写法的难点在于最后那步buy p而不是buy p fee因为这一笔的利润里已经扣过一次手续费不能重复扣。这种贪心和状态机 DP 在结果上等价只是表达方式不同。我的建议是面试时优先写 DP理由很现实DP 是汽车自动挡很多人记不住buy p还是buy p fee这种细节但两变量的状态转移几乎不可能写错而且它天然能推广到其他变种题。5. 实盘踩坑记录这些错误我犯了不止一次5.1 手续费重复扣除的坑最常见的新手错误就是手续费扣两次。有些人看完题解说“可以在买入时扣”于是把初始化改成hold -prices[0] - fee然后又保留卖出时扣手续费的分支结果每一笔交易成本多了2 * fee。这种错误很隐蔽因为样例可能刚好只涉及一笔交易算出来的利润只差一个 fee人眼不容易察觉。我的自检方法是拿一个简单用例跑prices [1, 3]fee 2。正确结果应该是 0因为 3 块卖掉还要交 2 块手续费净赚 0如果有任何代码返回负数或 -2说明手续费扣多了返回 1 之类更是完全错了。5.2 滚动变量新旧值串位前面讲空间优化时我强调过先更新cash再让hold使用新的cash在数学上通常会被max容错但这种写法很容易在面试追问时把自己绕进去。如果面试官接着问“如果现在改成带冷冻期你这样写还对不对”你只能承认不对。所以从 714 开始就养成“先用旧值计算全部新值再统一赋值”的习惯后面做 309、188 会省很多心。调试时还有一个技巧如果答案比预期大多半是哪里多赚了一笔如果答案比预期小大概率是手续费扣多了。先用暴力 DP 的二维版本和滚动版本对拍再拿小样例人工验算这是排查动态规划问题最快的方法。5.3 边界条件和零手续费退化fee 0时714 应该退化成 122。这是验证代码正确性最好的天然测试把fee设成 0跑几个你知道答案的用例看结果是否等于 122 的答案。比如prices [1, 3, 2, 8]fee 0时答案应该是 8。我再举一个容易出错的边界价格下降且始终覆盖不了手续费时最优是干脆不交易答案应该为 0。比如prices [5, 4, 3]fee 2任何买卖都是亏cash会一直保持 0。还有一点如果prices只有一个元素答案是 0因为一天之内无法完成一笔交易。很多递归式 DP 解法会在这类边界上产生额外分支滚动变量的写法天然不会因为它压根不进入循环。5.4 用手推样例验证逻辑我习惯在写完代码后手动推一个带“中间拐点”的样例比如prices [1, 4, 2, 8]fee 2。最优解是 1 买 8 卖得 5或者 2 买 8 卖得 4如果 1 买 4 卖、2 买 8 卖则得 1 4 5等等1 买 4 卖利润是4-1-2 12 买 8 卖利润是8-2-2 4总利润 5其实和 1 买 8 卖一样。这说明手续费导致合并交易和拆分交易有时等价但不总是。拿这个样例去跑代码看输出是否为 5能确认手续费扣法正确。手动推一遍能让你对状态含义形成肌肉记忆面试时即使紧张也能很快验证自己的公式。6. 股票题全家桶一套状态机框架通吃多个系列题6.1 通用状态机框架714 其实只是“股票买卖”大系列里的一环。整个系列都可以抽象成一个三维 DPdp[i][k][0]表示第 i 天结束已经完成了 k 次交易不持有股票的最大现金dp[i][k][1]表示第 i 天结束已经完成了 k 次交易持有股票的最大现金。这里“完成一笔交易”的计数可以约定在买入时消耗一次交易机会卖出时保持 k 不变也可以反过来约定关键是从头到尾保持一致结果不会改变。通用转移方程如下dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i] - fee) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])当 k 无限大时这个维度就可以完全去掉得到的就是 714 的转移方程。手续费只是第一行里多减一个fee。所以只要你把 714 的状态机理解透后续所有同类题都是往这个骨架上加限制条件。6.2 各题的变形点题号限制条件和 714 的核心差异需要怎么改121只允许一次交易k 固定为 1无手续费直接维护历史最低价两行代码搞定122无限次无手续费k 无限fee 0714 代码把 fee 设为 0 即可123最多两次交易k 固定为 2在状态里加 k 维度可以用四个滚动变量188最多 k 次交易k 是参数三维 DPk 大于 n/2 时退化成 122309无限次卖出后冷冻一天卖出后不能立刻买入补一个“冷冻期”状态或调整买入转移714无限次有手续费当前题两状态 卖时扣 fee这张表用得很顺手。面试官问“股票题你都会做吗”我就是这样答先说我了解统一的状态机框架然后对着题目往里套限制条件基本都能现场把转移写出来。比死背每一道题的具体代码靠谱得多。6.3 面试讲法建议怎么聊这道题才显得你真的懂如果面试官问 714我会按四步讲。第一步定义状态持有和不持有。第二步给转移方程解释为什么卖出要减 fee 而买入不减。第三步初始化第 0 天不持有时现金为 0持有股票要花掉prices[0]。第四步时间 O(n)、空间 O(1) 的分析。如果面试官追问“能不能贪心”可以顺势举一个反例比如前面说的[1, 3, 2, 8]加fee 2贪心做两次交易净赚 4DP 做一次交易赚 5这样就把劣势讲透了。如果还能补一句“把手续费放在买入端也等价”比如初始化hold -prices[0] - fee面试官会觉得你不是背题而是理解了解法背后的自由度。最后写代码时一定用滚动变量的标准写法跟肚子里讲的状态转移保持一一对应避免临场手滑。我自己刷这道题最大的收获不是记住两个变量的状态转移而是弄懂“状态定义才是 DP 的灵魂”。714 看起来只是 122 加了一个手续费但正是这个费用迫使你从“每段利润”的局部视角切换到“持仓状态”的整体视角。后来做 123、188、309我用的都是同一套状态机思路。如果你也在这道题上卡过建议先别看答案把第三节的递推自己推一遍尤其要亲手跑一遍第 5 节那个踩坑的例子。能把这个过程复现出来的人后面遇到任何股票买卖变种题都会觉得只是在同一个骨架上做微调。