算法题里有一类题目特别有意思它看起来简单到能用一句话讲完但背后藏着两种截然不同的解题世界观。买卖股票的最佳时机就是这样的题。它几乎是所有算法面试官的心头好也是很多人第一次感受到贪心与动态规划分界线的地方。我第一次做这道题的时候用暴力双重循环过了测试心里还挺得意后来被问到能不能只遍历一遍才意识到自己根本没摸到这道题的门。这篇文章我想把它彻底拆开讲透——一次交易的DP怎么写、贪心为什么成立、两个解法之间到底是什么关系以及怎么用一套状态机模板把后面所有变体多次交易、冷冻期、手续费、最多K笔全部打通。不管你是刚开始刷算法的新手还是想把这题讲给别人听的老手应该都能从这里拿到点东西。1. 先把题目和它的家族关系理清楚1.1 一次交易的原始版本到底在问什么原始题目是这样的给一个数组prices其中prices[i]表示某只股票第i天的价格。你只允许买入一次、卖出一次而且必须先买后卖不能做空问能获得的最大利润是多少。如果不能获利就返回 0。举个例子prices [7, 1, 5, 3, 6, 4]最优操作是第 2 天下标 1以 1 买入、第 5 天下标 4以 6 卖出利润 5。这道题的约束里有三个关键点很多人在读题时一扫而过但它们决定了你后面能写出什么解法。第一个是只允许一次交易这意味着你赚到的钱不能复投买入价永远是从零开始的支出。第二个是先买后卖所以任意时刻你只可能处于两种状态之一手里握着股票或者手里全是现金。第三个是不获利就返回 0这暗示我们允许不操作这个选项它天然就是收益 0。我见过不少人一上来就想找出最小值再找它后面的最大值思路方向是对的但经常栽在最小值可能出现在最大值后面这种细节上。正确的心智模型不是找两个极值点而是对每一天假设今天卖出我最理想的情况是什么——这个视角一转换后面贪心的写法就是水到渠成的事。1.2 为什么这道题会成为贪心与DP的分界线这道题的特殊之处在于它同时存在一个 O(n) 的贪心解和一个 O(n) 的动态规划解而且两个解都能正确通过。很多人刷完之后会产生一个疑惑既然贪心这么简洁为什么还要学 DP答案在于约束条件的变化。原始版本只允许一次交易贪心成立一旦允许无限次交易、或者加上冷冻期、手续费贪心的简洁写法立刻就失效了必须回到 DP 的状态机框架。所以这道题真正的价值不是学会一个技巧而是理解贪心是 DP 在特定约束下化简后的产物。你把这个关系搞清楚以后遇到任何变体都能从 DP 骨架出发去推导而不是每次碰运气地猜贪心对不对。我个人的建议是先用 DP 把题目做对再思考贪心能不能化简。顺序反过来的话你会形成看到股票题就想贪心的思维定式一旦题目加了条件就会翻车。DP 是兜底方案贪心是特定场景下的加速通道这个主次关系一定要摆正。2. 动态规划解法从二维状态到两个变量2.1 状态定义该怎么想才不容易错动态规划最怕的就是状态定义模糊。我用过很多种写法最后发现最稳的一种是把状态定义在第 i 天结束之后而不是第 i 天。这两个表述只差几个字但边界处理难度差很多。具体来说定义dp[i][0]表示第i天结束、手里不持有股票时的最大累计收益dp[i][1]表示第i天结束、手里持有股票时的最大累计收益。注意是结束而不是当天操作这样就把今天什么都不做这种转移天然包含进来了。为什么这么定义因为股票题的转移永远是两种动作叠加要么维持现状要么做一次切换。用天结束时的状态作为锚点维持现状就是dp[i-1][x]切换就是从另一个状态转移过来。这个框架建立起来之后你只需要回答一个问题从不持股变成持股要付多少钱答案是-prices[i]如果只允许一次交易从持股变成不持股要收多少钱答案是prices[i]。初始化的处理也有讲究。第 0 天结束时不持股的收益是 0没买也没卖持股的收益是-prices[0]第一天就买入支出全部花掉。这两个初值填对了循环从第 1 天开始跑就行。2.2 手推一遍状态转移表光看公式容易糊涂我们拿prices [7, 1, 5, 3, 6, 4]手算一遍。注意这道题只允许一次交易所以买入时前面不能有卖出收益买入状态只能写-prices[i]不能写dp[i-1][0] - prices[i]。这一点是这道题最容易被忽略的坑。天数 iprices[i]dp[i][0] 不持股dp[i][1] 持股070-7110-1254-1334-1465-1545-1第 2 天那一行解释一下dp[2][0] max(dp[1][0], dp[1][1] 5) max(0, -1 5) 4意思是第 2 天卖出手里的股票成本 1拿到 4 的收益。dp[2][1] max(dp[1][1], -5) max(-1, -5) -1意思是继续持有第 1 天买入的股票更划算因为第 2 天买要花 5成本更高。最后答案是dp[5][0] 5。手推一遍的意义在于你会看到dp[i][1]这一列里数字的变化规律——它其实一直在记录到目前为止见过的最低成本的负数。这个观察直接通向贪心解法我们后面再说。注意如果你把买入转移写成dp[i-1][0] - prices[i]这道题的答案会变成无限次交易的答案。因为一旦允许用之前的卖出收益来买入就相当于可以反复低买高卖了。这是新手最常踩的坑之一务必确认题目允许几笔交易。2.3 滚动变量的空间优化与代码二维数组版本已经能过题但空间是 O(n)。观察转移方程会发现dp[i][*]只依赖dp[i-1][*]所以完全可以用两个变量滚起来。这也是面试官喜欢追问的优化点。def maxProfit(prices): if not prices: return 0 # cash: 当天结束不持股的最大收益 # hold: 当天结束持股的最大收益 cash 0 hold -prices[0] for p in prices[1:]: # 只允许一次交易hold 只能来自直接买入 # 所以更新 cash 时用的是旧的 hold更新 hold 用的是 -p cash max(cash, hold p) hold max(hold, -p) return cash这段代码有两个细节值得说明。第一cash和hold的更新顺序在这道题里不影响结果因为hold的新值-p和cash无关但在无限次交易的版本里顺序就至关重要了这个坑我们会在第 5 节专门讲。第二hold初始化成-prices[0]而不是 0是因为手里握着股票这个状态本身就代表一笔支出如果初始化为 0等于白送一只股票逻辑就崩了。时间复杂度 O(n)空间 O(1)。这个版本我建议你能默写出来因为它是整个股票系列的骨架后面的变体无非是在转移方程上加东西。3. 贪心解法它凭什么是对的3.1 局部最优到全局最优的证明思路贪心的核心问题是凭什么局部最优能推出全局最优这道题的贪心策略是遍历过程中维护一个到目前为止的最低买入价对每一天计算如果今天卖出能赚多少取最大值。要证明它正确可以这样想。最优解一定是某个买入日 b配某个卖出日 s且 b s。对于固定的卖出日 s最优的买入日一定是[0, s-1]区间内价格最低的那一天——因为卖价固定时买价越低利润越高这是显然的。所以全局最优解一定形如某个卖出日 它之前的历史最低价。而我们的遍历每天都计算了这件事所以最大值一定被覆盖到。这就证明完了。你会发现这个证明根本没用到什么高深的东西就是把最优解长什么样描述清楚然后说明我们的枚举范围包含了它。这也是贪心证明的通用套路先刻画最优解的结构再证明你的策略能构造出这个结构。3.2 代码实现与边界处理def maxProfit(prices): if not prices: return 0 min_price prices[0] # 历史最低买入价 best 0 # 最大利润默认 0 表示可以不操作 for p in prices: if p min_price: min_price p # 找到更低的买点更新 else: best max(best, p - min_price) # 今天卖出能赚多少 return best这段代码里有几个容易出错的地方我一个个说。第一min_price初始化为prices[0]而不是float(inf)虽然用inf也能过但如果数组是空的用prices[0]会在前面就被if not prices拦掉逻辑更干净。第二best初始化成 0对应不操作这个选项题目要求不能获利就返回 0所以这是必须的。第三else分支不能省——如果今天创了新低那今天卖出肯定亏至少不赚没必要算直接更新买点即可这个写法里if/else其实可以合并成先更新min_price再算利润但要注意顺序先算利润的话会用到今天当买点的脏数据。实操心得我见过有人在else里写成best max(best, p - min_price)但如果把min_price的更新放在这个语句后面当p创了新低时会算出负数再被 max 掉虽然结果也对但多了一次无意义的比较。小数组无所谓数据量大时这种细节值得抠。3.3 贪心与DP的等价关系现在回到那个核心问题贪心和解 DP 到底什么关系我们把 DP 的hold那一路单独拎出来看。只允许一次交易时hold max(hold, -p)展开后其实就是hold -min(prices[0..i])。也就是说持股状态的最优值永远是到目前为止最低价的负数。再看cash max(cash, hold p)把hold替换成-min_price就变成了cash max(cash, p - min_price)——这正是贪心代码里的那一行。所以结论很明确这道题的贪心就是 DP 化简后的结果。之所以能化简是因为只允许一次交易这个约束砍掉了 DP 里的一整条转移路径用卖出收益再买入。一旦把这个约束去掉hold就不能只记最低价了它必须考虑之前赚到的钱贪心的化简立刻失效。这个认识比记住代码重要得多。4. 两种解法的对比与选型4.1 复杂度、可读性、可扩展性对照维度暴力枚举动态规划贪心时间复杂度O(n²)O(n)O(n)空间复杂度O(1)O(1)O(1)代码行数少中少可读性直观需要状态思维直观可扩展性差强弱适用约束小数据全部变体仅一次/无限次从表里能看出来暴力法在小数据量下其实是最容易理解的——两层循环外层枚举买入日内层枚举卖出日取最大值。它的价值在于验证当你写出 DP 或贪心后可以先用暴力法对拍一批随机数据确认答案一致再提交。这个习惯我强烈建议保留尤其是做变体题的时候。DP 的扩展性最强遇到最多两笔交易冷冻期一天这类新约束无非是状态多一维或者转移多一项。贪心代码最短但它的适用范围窄得可怜基本只在这道原始题和不限次数交易那题里好用。4.2 什么时候贪心会翻车我给个具体的判断题如果题目允许买入前必须先卖掉之前的持仓也就是可以多次买卖那维护一个最低价的贪心还能用吗答案是不能。原因很直接多次交易时买入的钱可能来自之前的卖出收益所以买入时的成本不再是绝对价格而是价格减去之前已赚的收益。一个看似很高的买入价如果你账户里已经赚了很多钱实际成本可能很低。贪心只盯着绝对价格就会漏掉这类最优解。举个反例感受一下prices [1, 2, 4, 2, 5]。不限次数交易时最优是 1 买 2 卖赚 12 买 4 卖赚 22 买 5 卖赚 3总共 6。但如果用一次交易版贪心去算它只会找全局最低价和后面的最高价算出来 5-14明显不对。不过有意思的是不限次数交易的这个版本其实有另一个更简单的贪心把每一天和前一天比只要是上涨的就把这段涨幅加到答案里。def maxProfit_inf(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 化简出来只不过这次化简用到的约束是交易次数不受限。所以你看贪心的形态变了但贪心等于特定约束下的DP化简这个本质没变。5. 用一个状态机模板打通整个股票系列5.1 无限次交易与上涨段求和无限次交易的 DP 写法跟一次交易版只差一个符号的位置。买入时不再用-p而是用cash - p因为你可以用之前赚的钱来买。def maxProfit_inf_dp(prices): if not prices: return 0 cash 0 hold -prices[0] for p in prices[1:]: # 关键必须先算新的 cash再算新的 hold # 否则 hold 可能用当天的 cash 买入造成当天买当天卖 new_cash max(cash, hold p) new_hold max(hold, cash - p) cash, hold new_cash, new_hold return cash注意这里我用new_cash和new_hold两个临时变量。如果偷懒写成先cash max(cash, hold p)再hold max(hold, cash - p)那更新hold时用的是已经卖出后的cash等价于允许当天买、当天卖这在 A 股规则下是不合法的虽然对结果可能没影响因为当天买卖不赚钱但逻辑上是错的加上手续费后就会算出错误答案。这个坑我在第 6 节还会再提。5.2 最多K笔交易、冷冻期、手续费怎么改最多 K 笔交易。状态需要加一维表示已经完成了多少笔完整的买卖。这里有个小技巧把持有股票看作第 j 笔交易的中间态不持股看作第 j 笔交易完成后的状态。def maxProfit_k(k, prices): if not prices or k 0: return 0 # sell[j]: 完成 j 笔交易且不持股的最大收益 # buy[j] : 完成 j 笔交易第 j 笔进行中且持股的最大收益 sell [0] * (k 1) buy [-float(inf)] * (k 1) for p in prices: for j in range(k, 0, -1): sell[j] max(sell[j], buy[j] p) buy[j] max(buy[j], sell[j - 1] - p) return sell[k]两个细节必须注意。第一内层循环要从大到小遍历 j因为buy[j]依赖sell[j-1]正序遍历会导致同一笔交易被重复利用等于把一笔交易拆成好几笔。第二buy[0]初始化成负无穷因为还没做任何交易就持股是不合法的状态如果初始化成 0 会凭空多出收益。sell[0] 0是合法的代表什么都没做。冷冻期。卖出后第二天不能买所以需要三个状态持有、不持有且今天可以买、不持有但处于冷冻。def maxProfit_cooldown(prices): if not prices: return 0 hold -prices[0] # 持股 free 0 # 不持股且可以买入 frozen -float(inf) # 不持股但明天才能买 for p in prices[1:]: new_hold max(hold, free - p) new_free max(free, frozen) new_frozen hold p hold, free, frozen new_hold, new_free, new_frozen return max(free, frozen) **手续费。** 最简单卖出时扣掉手续费即可其余不变。 python def maxProfit_fee(prices, fee): if not prices: return 0 cash 0 hold -prices[0] for p in prices[1:]: new_cash max(cash, hold p - fee) new_hold max(hold, cash - p) cash, hold new_cash, new_hold return cash把这三种改造放在一起看你会发现规律所有变体都是在状态定义和转移方程上做加法骨架永远是那几个变量滚来滚去。记住骨架变体就是填空。6. 常见问题与调试避坑实录6.1 高频错误速查表现象可能原因修复方法一次交易算出无限次答案买入写成dp[i-1][0] - p改为-p答案是负数没考虑不操作选项结果初始化为 0取 max冷冻期答案偏大卖出当天就允许买入用三个状态区分K 笔交易答案偏大内层 j 正序遍历改成从 k 到 1 倒序空数组报错没做边界判断开头加if not prices无限次交易手续费算错用了旧的 cash 买入用临时变量存新值这张表里的每一条我都在实际写代码或帮人调代码时遇到过。尤其是第一条和第四条几乎是必踩的坑。第一条的迷惑性在于从公式上看dp[i-1][0] - prices[i]好像更完整但它偷偷改变了题目语义。第四条的迷惑性在于正序遍历在最简单的无限次交易版本里也没问题因为状态只有两个一旦引入 K 维就暴露了所以很多人是在写 K 笔交易时才第一次栽在这里。6.2 手写代码时的几个习惯我分享几个自己养成的习惯这些在面试手写代码时特别有用。第一个习惯是先写暴力再写优化。暴力版本虽然慢但它能帮你把题意理解正确而且可以作为对拍的标准答案。我平时会用random生成 1000 组随机小数组暴力跑一遍、DP 跑一遍结果不一致就打印出来看。这个对拍流程能省掉大量改了 A 结果 B 又错了的来回折腾。第二个习惯是在纸上画状态图。虽然这里不能画图但你可以在草稿纸上画三个圈代表三个状态箭头代表转移箭头上标注加减项。状态图一画转移方程基本就是照抄不容易漏状态也不容易写错符号。我做冷冻期那道题的时候就是靠画图才发现漏了冷冻状态这一维。第三个习惯是永远检查数组长度为 0 和 1 的边界。长度 0 要直接返回 0长度 1 时无法交易也要返回 0。这两个 case 用if not prices加循环从下标 1 开始基本就能覆盖。别小看这个线上跑的类型检查和边界判断能挡掉一大批低级错误。第四个习惯是变量命名带上语义。用cash、hold、frozen这种一眼能看出含义的名字别用a、b、tmp1、tmp2。状态机类的题目变量名起得好代码基本能自解释回看时也不容易搞混。我见过有人用dp0、dp1、dp2写成冷冻期过两天自己都看不懂哪个是哪个状态。最后说一个心态上的经验。这类题最怕的是背题——把某个解法背下来遇到变体就套。真正管用的做法是抓住状态是什么、转移是什么、初始值是什么这三个问题每个变体都从零推一遍。推得多了你会发现整个股票系列其实就是一套状态机在换衣服题目再怎么变答案都在那三行转移方程里。我个人在实际写这类题时的体会是先把 DP 写对拿到保底分有时间再去想贪心能不能化简。别一上来就追求最优雅的写法把逻辑跑通比什么都重要——毕竟代码是写给未来的自己和同事看的不是写给编译器炫技的。