1. 同一道壳子下的六张面孔买卖股票问题族到底在考什么我第一次在面试现场被问到「买卖股票的最佳时机」写出来的是一段两层 for 循环。面试官扫了一眼问时间复杂度我说 O(n²)他点点头接着追问「那如果允许交易很多次呢还能更快吗」那一瞬间我才意识到这道题不是一个孤立的题目它背后站着一整个问题族。后来我自己带人刷题、也在一些数据序列处理的活儿里用到类似的建模思路才慢慢把脉络理清楚——贪心和动态规划在这类问题上不是两个对立的选项而是同一套状态思想在不同约束下的两种投影。这篇文章我想干的事情很具体把「买卖股票的最佳时机」这一族题目从贪心的角度、从状态机 DP 的角度各拆一遍把转移方程为什么长这样、初始化为什么不能写 0、冷冻期和手续费怎么塞进去、k 次交易什么时候会退化全部讲透。不管你是刚学完 DP 想找一道题练手还是已经刷过但每次都要重新推公式下面的内容应该都能让你少绕点路。1.1 六道变体的参数矩阵先把家族成员摆出来。网上流传的版本不止六个但核心骨架就是下面这几张面孔其他都是它们的排列组合。题号交易次数约束额外限制主流通解时间复杂度121最多 1 笔无贪心 / 线性 DPO(n)122无限笔无贪心 / DPO(n)123最多 2 笔无状态机 DPO(n)188最多 k 笔无状态机 DPO(nk)309无限笔卖出后冷冻 1 天状态机 DPO(n)714无限笔每次交易收手续费贪心 / DPO(n)看懂这张表的关键是发现所有题的共同约束只有一条任意时刻手上最多持有一股。交易次数、冷冻期、手续费全都是在这条主干上挂的枝节。换句话说只要你能把「最多持有一股」这件事翻译成状态剩下的都是往状态上贴标签。1.2 「最多持有一股」为什么是整套建模的起点很多人推不出来转移方程根本原因不是数学不好而是没意识到这条约束的真正含义。它意味着你在第 i 天的身份只有两种——手里拿着股票持仓或者手里没有股票空仓。不可能既拿着又空着也不可能拿着两股。于是「第 i 天的最优解」这件事被劈成了两个子问题第 i 天持仓时的最大收益是多少第 i 天空仓时的最大收益是多少。这两个子问题互相喂数据——今天持仓可能是因为昨天就持着没动也可能是昨天空仓今天买的今天空仓可能是昨天就空着也可能是昨天持仓今天卖了。这种「今天的我由昨天的我决定」的结构就是状态机 DP 的全部内涵。我常跟新人打一个比方把每天的决策想象成坐在赌桌前你手里要么攥着一张牌要么空着手。攥着牌的时候你不能再去拿牌空着手的时候你可以拿一张也可以直接走人。你唯一要记录的就是「此刻手上有没有牌」以及「我已经换了几轮牌」。这个比喻不精确但能帮你在写方程之前先在脑子里把状态画出来。1.3 交易次数的口径一次买加一次卖才算一笔这是最容易出错、也最少被强调的一点。几乎所有版本的定义都是一笔交易 一次买入 一次卖出。买入当天不计数卖出那天才把交易数加一或者反过来买入那天计数卖出不加。两种口径都能跑通但绝不能混用。为什么这件事值得单独拎出来说因为当你写dp[i][j][1]的时候那个j到底代表什么直接决定了转移方程里该用j-1还是j。如果用「卖出计数」那么从空仓到持仓这一步会消耗一次交易额度如果用「买入计数」则是从持仓回到空仓那一步消耗额度。两种写法等价但你必须选定一个并全程贯彻。我在下面所有代码里统一采用卖出时计数的口径也就是买入不消耗额度卖出那一刻j才加一。2. 峰值谷值贪心它在 121 和 122 里成立的真正理由贪心在这族题里名声两极分化。有人觉得它简洁优雅有人觉得它是玄学写出来心里没底。区别就在于你是背下了结论还是理解了它为什么成立。这一节我按「先看懂 121 里的那个变量再看懂 122 里的差分分解最后看贪心什么时候会塌房」的顺序走一遍。2.1 121 的贪心一个变量顶掉一层循环暴力解法的思路是枚举买入日和卖出日套两层循环复杂度 O(n²)。贪心把它压成 O(n)靠的是一个观察如果你确定了卖出日是第 i 天那么最优的买入日一定是第 i 天之前价格最低的那一天。这句话几乎不需要证明——同样是卖出价买入价越低赚得越多没有第二种选择。所以整个算法只需要维护一个变量min_price记录「截至昨天为止见过的最低价格」然后拿今天的价格减它得到的候选收益和历史最优比一下。def maxProfit(prices): if not prices: return 0 min_price prices[0] best 0 for p in prices: min_price min(min_price, p) # 先更新历史最低价 best max(best, p - min_price) # 再算今天卖出的收益 return best这段代码有两个细节值得掰开。第一个是更新顺序。我先min再算收益意味着如果今天恰好是历史最低价p - min_price会等于 0不会影响结果。如果反过来先算收益再更新min_price那么遇到「今天是历史最低」的情况p - min_price会变成正数相当于在同一天既买又卖这是题目禁止的。顺序反过来写不会让答案变大因为它俩相等的时候收益就是 0但在别的变体里这个顺序错误会导致实实在在的偏差所以习惯要从这里养成。第二个是收益下界。best初始化为 0表示「一笔都不做」这个选项永远合法。题目里有个隐含约定不能赚钱就不交易。如果把best初始化成float(-inf)那么遇到单调递减的序列就会返回负数这是错的。2.2 122 的贪心差分分解给出的答案上界122 允许无限次交易很多人第一反应是「那不是每天都在最高点卖、最低点买就行了吗」。问题是最高点最低点只能在事后才知道在线策略不能偷看未来。好在这题恰好有一个更朴素的结论把所有相邻两天之间的正差价加起来就是答案。def maxProfit(prices): profit 0 for i in range(1, len(prices)): diff prices[i] - prices[i - 1] if diff 0: profit diff return profit为什么这个式子成立我用「上界 可达」两步来说明。上界部分任意一笔交易从第 i 天买入、第 j 天卖出利润是prices[j] - prices[i]。把它拆开prices[j] - prices[i] (prices[i1] - prices[i]) (prices[i2] - prices[i1]) ... (prices[j] - prices[j-1])也就是说任何一笔交易的利润都等于它跨过的那些相邻差分的和。如果某天是下跌的差分为负那这天一定在某个「亏损区间」里累加时会把利润拉低。所以任意交易方案的总利润都不会超过「所有正差分之和」。这是一个上界。可达部分能不能真拿到这个上界能。策略非常简单——只要今天比昨天涨就当作昨天买入、今天卖出。每个上行段都完整吃掉每段正差分都不落下。因为每天允许买卖这个策略完全合法。上界可达所以它是最优解。这个证明思路的价值远不止这道题。凡是「允许把一个大区间拆成若干小区间分别处理」的贪心证法基本都是这个套路先证明拆分后的累加是原问题的上界再构造一个方案顶到这个上界。2.3 贪心什么时候会塌房309 和 714 给出的反例现场讲完两个成功案例必须泼一盆冷水。同样的正差分累加到了 309 和 714 上就会直接算错。先说 309 冷冻期。假设价格序列是[1, 3, 2, 4]规则要求卖出后第二天不能买。按 122 的贪心正差分会算出(3-1) (4-2) 4。但真实最优是多少在第 1 天买价格 1、第 2 天卖价格 3赚 2然后第 2 天卖出后第 3 天进入冷冻不能买最早第 4 天才能买可第 4 天只有一天买了也没法卖。所以最优是 2而不是 4。贪心多算了。再算 714 手续费。设fee 2价格序列是[1, 4, 5]。122 式的贪心累加正差分得(4-1) (5-4) 4扣两次手续费要扣 4净收益 0。但最优其实是第 1 天买、第 3 天卖赚5 - 1 - 2 2。正差分累加把一笔本来该合并的交易拆成了两笔白交了一次手续费。结论很清楚贪心的正确性依赖于约束的形状。约束一旦改变了「持有和空仓之间能否自由切换」的规则原本的拆分解法就不再成立。这时候老实上状态机 DP别硬凑。3. 状态机 DP一套骨架打通所有变体如果你只打算记一种解法那就记这一套。它写起来比贪心长但六道题全都能套而且每一步都有明确的物理含义不用赌运气。3.1 三维状态的定义与含义对齐先约定符号dp[i][j][0]表示第 i 天结束时、已经完成了 j 笔交易、并且当前空仓的最大收益dp[i][j][1]表示第 i 天结束时、已经完成了 j 笔交易、并且当前持仓的最大收益。这里「已经完成 j 笔」按前面说的卖出计数口径理解买入不占额度卖出那一刻额度 1。把两个状态各自的来源捋一遍转移方程自然就出来了今天空仓要么昨天就空着今天啥也没干要么昨天持仓今天卖了卖出让交易数加一。所以dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j-1][1] prices[i])。今天持仓要么昨天就持着今天继续拿着要么昨天空仓今天买入买入不加额度。所以dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])。注意第二个式子里右边用的是dp[i-1][j][0]而不是dp[i-1][j-1][0]这正是「买入不计数」的直接体现。如果你选了买入计数这里就该反过来。两种写法不要混。3.2 初始化里的负数陷阱为什么不能图省事写 0新手最容易栽的地方是初始化。常见错误写法是dp[0][j][0] 0、dp[0][j][1] 0觉得「反正 max 会挑大的」。这样写会出大问题。dp[0][j][1]的含义是「第 0 天结束、已经完成 j 笔、手里还拿着股票」。第 0 天你想持仓唯一可能是当天买入收益是0 - prices[0]本来是空仓 0 元花掉prices[0]买了股票。它绝不可能等于 0因为 0 意味着「白拿了一股」这是不可能的白日梦。如果初始化成 0程序就会算出一个虚高的、靠凭空发股票赚来的收益。正确做法是NEG float(-inf) # dp[0][0][0] 0 第 0 天不持股收益 0 # dp[0][0][1] -prices[0] 第 0 天买入收益为负的买入价 # dp[0][j][*] NEG 对 j 1第 0 天不可能完成任何一笔交易用负无穷而不是 0 去填充非法状态是这类「状态有限制」的 DP 的通用习惯。负无穷在这里扮演的是「此路不通」的路障max一碰到它就会自动把这条非法路径排除掉。3.3 空间压缩从三维数组到两行滚动变量三维数组空间是 O(nk)遇到 n 和 k 都不小的情况会爆内存。仔细观察转移方程dp[i]只依赖dp[i-1]所以第一维可以直接压掉用两个长度为k1的数组滚动。关键是压缩之后的更新顺序。先看遍历方向j必须从大到小遍历。def maxProfit(k, prices): if not prices: return 0 n len(prices) k min(k, n // 2) # 交易次数上界剪枝后面细讲 NEG float(-inf) hold [NEG] * (k 1) # 持仓状态 cash [0] * (k 1) # 空仓状态 hold[0] -prices[0] for i in range(1, n): p prices[i] for j in range(k, 0, -1): # 逆序保证用到的是上一轮的旧值 cash[j] max(cash[j], hold[j] p) hold[j] max(hold[j], cash[j - 1] - p) return cash[k]为什么必须逆序看hold[j]的更新它用到cash[j-1]。如果j从小到大遍历那么更新到j的时候cash[j-1]已经被这一轮改过了语义就变成了「今天卖了又拿这笔钱立刻再买」虽然在这道题的数值上未必导致错误答案同日买卖利润为 0max 通常不会让它变差但这个写法在加冷冻期、手续费之后会直接算错。逆序遍历能保证cash[j-1]还是上一轮的旧值语义干净不用去纠结特例。这个顺序问题是我当年 debug 最久的一个坑没有之一。3.4 用 123最多两笔验证骨架是否可靠拿 123 做一次对照实验把上面的骨架原封不动套上去令k 2跑一遍[3,3,5,0,0,3,1,4]得到 6第 4 天 0 买入、第 6 天 3 卖出赚 3第 7 天 1 买入、第 8 天 4 卖出赚 3合计 6。再手算验证一遍答案一致。这个过程值得你自己动手走一遍感受一下通用骨架的好处你不需要为每一道题重新想一套逻辑只需要改两个地方——k的值以及转移方程里要不要多挂一个状态。这种「一次想通、处处套用」的结构化思路才是刷算法题真正能带走的收益。4. 冷冻期、手续费、k 次交易把约束挂到状态上通用骨架跑通以后剩下的工作就是把各种约束翻译成状态。这一节的三个改动覆盖了绝大多数变体。4.1 309 冷冻期三状态方案与变量命名冷冻期的规则是一旦卖出第二天不能买入。注意它限制的是买入卖出本身不受限。翻译成状态就是「今天想买」这件事要额外看一眼「昨天是不是刚卖」。一种直观的写法是用四个变量区分身份但滚起来容易乱。我推荐三状态版本代码短且好记def maxProfit(prices): if not prices: return 0 hold -prices[0] # 今天收盘时持仓 sold 0 # 今天刚卖出明天将进入冷冻 free 0 # 空仓且可以随时买入不在冷冻期 for p in prices[1:]: new_hold max(hold, free - p) # 只能从 free 买不能从 sold 买 new_sold hold p # 今天卖昨天必须持仓 new_free max(free, sold) # 昨天就空着或者昨天卖了今天解冻 hold, sold, free new_hold, new_sold, new_free return max(sold, free)三个变量的语义边界卡得很死hold是持仓sold是「今天卖出、明天被冻」free是「空仓且明天能买」。买入只能从free出发这一行就是冷冻期约束的全部体现。这里有个特别容易翻车的点必须先算完所有新值再统一赋值。我上面用了new_*三个临时变量就是为了避开「算new_sold时hold已经被覆盖」这种顺序 bug。用 Python 的元组同时赋值其实也能解决但用临时变量更直观读代码的人一眼就知道哪些是旧值哪些是新值。4.2 714 手续费在买入扣还是在卖出扣差别在哪手续费有两种扣法买入时扣、卖出时扣。两种在数学上等价因为一笔交易总共只收一次无非是把成本记在起点还是终点。但从代码可读性看扣在卖出时更自然因为「收益 卖出价 - 买入价 - 手续费」符合人的直觉。DP 版本def maxProfit(prices, fee): if not prices: return 0 hold -prices[0] cash 0 for p in prices[1:]: hold max(hold, cash - p) # 买入不扣费 cash max(cash, hold p - fee) # 卖出时扣费 return cash注意hold先更新、cash后更新这段顺序。这样写允许「今天买今天卖」但这种情况的净收益是-p p - fee -fee 0max会把它丢掉所以不影响正确性。如果你想彻底避免歧义也可以先存一份旧的hold再算cash。这题还有一个经典的贪心写法值得单独看def maxProfit(prices, fee): profit 0 buy prices[0] for p in prices: if p buy: buy p # 找到更低的买点 elif p buy fee: profit p - buy - fee buy p - fee # 关键一行 return profitbuy p - fee这行是整段代码的灵魂。它的意思不是「以 p-fee 的价格重新买入」而是「把当前这笔交易的卖点临时挂在这里」。如果后面价格继续涨比如从buyfee涨到更高的位置前面的收益已经落袋新的一段再单独结算两段加起来刚好等于「一直持有到最高点」的收益手续费只交了一次。如果后面跌了p buy会把它当作新的买点说明前面那笔确实该结束。这个「减掉 fee 再当作新买点」的技巧是这题最值得记住的一句话。4.3 k 很大时的剪枝为什么 k 要砍到 n//2188 题里k可能给到10^9直接开k1长度的数组会 MLEO(nk) 的循环也会 TLE。但仔细想想一天最多参与一笔交易买入或卖出n 天最多也就做n//2笔有效交易。如果k n//2交易次数约束实际上已经失效题目退化成 122 那种无限次的情况。所以开头加一行k min(k, n // 2)复杂度立刻从 O(nk) 掉到 O(n²) 以下能过所有测试点。这个剪枝不是什么奇技淫巧而是对问题规模的正确认知——先想清楚参数的有效上界再决定开多大的数组这个习惯在工程代码里同样重要。5. 排查实录我在这几道题上踩过的五个坑前面讲的是「应该怎么写」这一节讲「写错了会怎样」以及怎么一步步定位。这些坑我都真踩过不是从题解里抄来的。5.1 坑一初始值偷懒写 0程序开始凭空印钞最典型的一次我在写 123 的时候把hold数组全初始化为 0跑出来一个比正确答案大得多的数。当时百思不得其解以为是转移方程推错了。后来把dp[0][1][1]单独打印出来看到它是 0才反应过来——这个状态表示「第 0 天完成 1 笔交易还持有股票」这本来就是不可能的事我却给了它一笔「免费股票」。定位这类问题的方法很土但很有效在数组初始化的下一行把每个非法状态单独打印出来确认它们确实是负无穷。如果你的语言里没有负无穷用一个足够小的数比如-10**9代替并在最后检查答案有没有被这个哨兵值污染。5.2 坑二交易次数的方向前后不一致有一次我转移方程的这两行是这么写的cash[j] max(cash[j], hold[j] p) hold[j] max(hold[j], cash[j - 1] - p)第一行卖出加了一次额度那买入就该不加额度。但如果我在另一处写成cash[j-1] - p之外的cash[j] - p就会导致同一笔交易被重复计数或者完全不计。判断标准只有一个数一数从开始到结束一次完整的买卖到底让 j 增加了多少。必须是恰好 1。写完方程以后手动模拟一笔交易看 j 有没有正确 1这个自检只需要 30 秒能省掉半小时 debug。5.3 坑三滚动数组的更新顺序前面 3.3 已经说过但还是值得再强调。压缩掉第一维以后你对「旧值」和「新值」的依赖变得非常隐蔽。判断顺序的方法很简单把dp[i][j][*]的方程写出来看某个变量依赖的是第 i 轮还是第 i-1 轮再决定遍历方向。如果更新j时用到的是j-1的上一轮值就逆序遍历如果用到的是同轮值就正序。冷冻期那题因为状态多了我会直接开临时变量宁可多占一点内存也不给自己留顺序上的隐患。这种「清晰优先于省一个变量」的取舍在算法和工程里同样成立。5.4 坑四n 小于等于 1 的边界直接被忽略prices长度为 1 时任何交易都做不成答案必须是 0。但很多写法在prices[0]上就崩了——如果数组为空prices[0]直接越界。我建议所有这类函数的第一行都写if not prices: return 0然后再处理长度为 1 的情况。长度 1 时循环体不执行hold[0] -prices[0]、最后返回max(cash[k], 0)或者直接返回cash[k]前提是cash初始化正确自然给出 0。这个习惯的价值是边界条件不是特例而是问题定义的一部分。你先想清楚「输入为空、输入只有一个元素」这些退化情况下答案应该是什么再写代码很多 bug 压根不会出现。5.5 坑五手续费贪心里那个判断写成714 的贪心解法里判断条件是p buy fee还是p buy fee我用。原因是为了和后面的buy p - fee配合。如果写成那么当p buy fee时会触发一次「收益为 0」的卖出然后buy被更新成p - fee buy数值上没变化但逻辑上白忙一场。虽然最终答案通常不受影响0 收益不会让结果变差但这类「等号陷阱」在别的题里是会实实在在出错的所以我习惯性地在严格大于才触发结算。写这类条件判断时我的一般原则是只有当「净收益严格为正」时才动作边界上保持不动这样最不容易出错。6. 把这套思路搬到真实场景从行情序列到状态机建模刷题刷到这个程度如果只停留在「能 AC」收获其实有限。更有意思的是这套「两状态 次数维度」的建模方式在很多看起来不相关的问题里都能复用。6.1 怎么快速识别问题里的「持有/不持有」二值状态判断一道题能不能用这套骨架我通常问自己三个问题。第一个是否存在一个资源它在某个时刻要么被你占用、要么不被占用且不能同时占用两份股票里的「持仓」符合库存调度里的「机器是否被某任务占用」符合充电桩里「车位是否空闲」也符合。第二个状态的切换是否有代价或者限制比如买入要花钱、卖出有手续费、切换后要冷却一段时间。第三个是否存在一个总量约束次数、容量、时间窗需要被跟踪这就是j维度。三个问题都答「是」那就基本上是同一类问题可以套状态机 DP。前不久我在处理一个任务调度的小工具时就遇到过「每个任务最多被重启 k 次、重启后要冷却一整个执行周期」的场景几乎和 309 一模一样把状态定义照搬过去二十分钟就搞定了。6.2 从 O(n²) 到 O(n) 的通用降维直觉暴力枚举两端点的题目往往都有一个「只需扫描一次」的优化。121 里靠的是维护前缀最小值122 里靠的是差分分解。它们的共同特征是把一个二维的「配对」问题转化为一维的「累积」问题。判断能不能这么做的信号是决策是否具有单调性。如果「今天做了某个选择明天的选择空间只会更小或者不变」那就可能出现贪心或线性 DP。反过来如果今天的选择会让明天多出一堆额外限制冷冻期就是典型那你还是老实上 DP别想着一步到位。6.3 工程里什么时候不该用贪心最后说一句掏心窝子的。贪心在竞赛里好用但在真实业务代码里我通常会先问一句「这个最优性有严格证明吗边界条件考虑全了吗」。如果答案是否定的我宁愿写那个看着笨、但每一步都有明确物理意义的 DP 版本。因为线上数据不会像测试用例那样规整贪心在某个奇怪的价格序列上算错一点点损失可能是真金白银。DP 的转移方程虽然啰嗦但它的正确性是可以在纸上验证的这一点在工程里比「代码短」值钱得多。这六道题我断断续续折腾了两年多每次重做都会有新体会。最近一次是把它讲给一个刚转行的朋友听讲到hold和cash两个状态的名字时他忽然说「原来就是手里有没有东西啊」。那一刻我才发现把复杂的东西讲成一句人话比写出漂亮的转移方程更难也更有价值。