企业官网建设流程全解析

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 直接拿到 8，4 再拿到 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 次交易限制，这个顺序错误就会实实在在造成 WA（Wrong 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手推一遍：

第 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 = 1，2 买 8 卖利润是8-2-2 = 4，总利润 5，其实和 1 买 8 卖一样。这说明手续费导致合并交易和拆分交易有时等价，但不总是。拿这个样例去跑代码，看输出是否为 5，能确认手续费扣法正确。手动推一遍能让你对状态含义形成肌肉记忆，面试时即使紧张，也能很快验证自己的公式。

6. 股票题全家桶：一套状态机框架通吃多个系列题

6.1 通用状态机框架

714 其实只是“股票买卖”大系列里的一环。整个系列都可以抽象成一个三维 DP：

dp[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 各题的变形点

这张表用得很顺手。面试官问“股票题你都会做吗”，我就是这样答：先说我了解统一的状态机框架，然后对着题目往里套限制条件，基本都能现场把转移写出来。比死背每一道题的具体代码靠谱得多。

6.3 面试讲法建议：怎么聊这道题才显得你真的懂

如果面试官问 714，我会按四步讲。第一步，定义状态：持有和不持有。第二步，给转移方程，解释为什么卖出要减 fee 而买入不减。第三步，初始化：第 0 天不持有时现金为 0，持有股票要花掉prices[0]。第四步，时间 O(n)、空间 O(1) 的分析。

如果面试官追问“能不能贪心”，可以顺势举一个反例，比如前面说的[1, 3, 2, 8]加fee = 2，贪心做两次交易净赚 4，DP 做一次交易赚 5，这样就把劣势讲透了。如果还能补一句“把手续费放在买入端也等价”，比如初始化hold = -prices[0] - fee，面试官会觉得你不是背题，而是理解了解法背后的自由度。最后写代码时一定用滚动变量的标准写法，跟肚子里讲的状态转移保持一一对应，避免临场手滑。

我自己刷这道题最大的收获，不是记住两个变量的状态转移，而是弄懂“状态定义才是 DP 的灵魂”。714 看起来只是 122 加了一个手续费，但正是这个费用迫使你从“每段利润”的局部视角，切换到“持仓状态”的整体视角。后来做 123、188、309，我用的都是同一套状态机思路。如果你也在这道题上卡过，建议先别看答案，把第三节的递推自己推一遍，尤其要亲手跑一遍第 5 节那个踩坑的例子。能把这个过程复现出来的人，后面遇到任何股票买卖变种题，都会觉得只是在同一个骨架上做微调。