动态规划状态机：五道股票买卖题一网打尽

本来想把这五道股票题拆开一篇篇写但刷到后面发现它们完全是同一个套路层层递进从“一次买卖”到“无数次买卖”再到“最多两次”“最多k次”最后加一个冷冻期。状态机模型一以贯之区别只在状态定义和转移边数。这篇文章就把这五道题当作一个系列来拆每一题讲清楚状态设计、递推逻辑和容易踩的坑最后再总结这组题通用的分析框架。适合正在刷动态规划、准备面试或者刚看完代码随想录对应章节还不太理解“为什么这么定义状态”的同学。1. 把五道股票题放在一起看它们都长在同一根骨架上先说说为什么这几道题值得放在一起刷。121、122、123、188、309这五道题表面看是“买卖次数不同”“有没有冷冻期”的区别实际上底层都是同一个东西二维状态机动态规划。每一题都在做同一件事——维护某一天结束后处于某个“持仓/空仓”状态下的最大利润。很多初学者第一反应是用贪心或者模拟比如122题确实能贪心解121题也能用“记录历史最低点”的扫描法解。但问题是一旦遇到123和188这种带有“交易次数上限”的题贪心立刻失效暴力模拟又会写出很长很难维护的分支判断。所以刷这组题的正确姿势是从121开始就建立状态机DP的思维后面所有题都是在这个骨架上加状态、加维度。我个人在训练营里把这组题排在一起刷之后最大的感受是动态规划题最难的永远是“状态定义”这一步而不是递推公式的代码实现。定义想清楚了转移方程是水到渠成的事定义想不清楚代码写多少遍都会在边界条件上翻车。这五道题的建议学习顺序其实也有讲究121是单一维度入门122让你理解“状态覆盖所有天数”的思考方式123引入“交易次数”这个第二维度188把“固定两次”泛化成“参数k次”309则是在状态图上加一条“冷却”边。按这个顺序刷每一题都是上一题的一个小改动而不是新的难题。2. 121题用“持有/不持有”两个状态拆干净一次买卖2.1 为什么扫描法可行但我还是推荐DP121题的经典非DP解法是从左到右扫描维护一个minPrice每天计算prices[i] - minPrice取最大值。这样做的正确性在于一次买卖的利润只取决于“卖的那天”和“之前最低的买点”贪心可以覆盖。但我的建议是这题就老实写DP而且要把dp[i][0]和dp[i][1]这套定义刻进脑子里。原因很简单121题如果用扫描法过去了122题你又会尝试贪心123题一出现“最多两次”你会发现贪心没法简单扩展最后还得回来学DP。绕了一圈不如第一题就把状态机模型的根基打好。2.2 状态定义与递推公式约定每一天有两个状态dp[i][0]第i天交易结束后手里持有股票时的最大利润dp[i][1]第i天交易结束后手里不持有股票时的最大利润这里“持有”和“不持有”指的是当天收盘后的持仓状态不是当天是否发生了买卖。初始值dp[0][0] -prices[0]第0天买入利润为负的股价dp[0][1] 0第0天不买利润为0递推公式dp[i][0] max(dp[i-1][0], -prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])dp[i][0]的含义是要么前一天就持有今天继续捂着不动要么今天是第一次买入此时之前没有过任何交易所以成本就是-prices[i]不需要用dp[i-1][1]去减。dp[i][1]的含义是要么前一天就没有持股今天继续空仓要么前一天持股今天卖出利润等于前一天持股的利润加上今天的股价。2.3 为什么“买入”不用dp[i-1][1] - prices[i]这是121和后面几题最大的区别点也是理解整组题的关键121题限制只能买卖一次所以在dp[i][0]的转移里只允许“第一次买入”。如果你写成dp[i-1][1] - prices[i]那就意味着你可以先卖一次再买一次这已经构成两次交易了。理解了这个区别再看后面122题的公式你会瞬间明白为什么它只改了一行。空间优化版本的代码如下hold和cash两个变量滚动更新public int maxProfit(int[] prices) { int hold -prices[0]; int cash 0; for (int i 1; i prices.length; i) { int prevHold hold; int prevCash cash; hold Math.max(prevHold, -prices[i]); cash Math.max(prevCash, prevHold prices[i]); } return cash; }我见过的常见坑是两个一是忘记初始化hold -prices[0]导致第一天之后的所有“买入”都从0开始算利润全部偏大二是在dp[i][0]的转移里加入了dp[i-1][1] - prices[i]虽然这道题答案可能碰巧没错因为只允许一次买入时空仓再买其实赚不到额外好处但到123题就会出大问题。3. 122题允许无数次买卖差别只是买入那行3.1 递推公式的“一处改动”122题允许任意多次买卖只要每次买入前手里没有股票即可。这时候状态转移变成dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])和121题对比唯一区别是买入时的成本计算dp[i-1][1] - prices[i]。这里dp[i-1][1]表示昨天收盘时手里没股票并且已经通过若干次买卖积累了利润今天再买入当然要基于这个利润去扣成本。3.2 一个直觉化的理解方式如果不看公式用大白话说无数次买卖的约束只有“手里最多一支股票”所以只要昨天是空仓今天就能买入买入后的利润自然要继承昨天空仓时的利润。这也是为什么122题的dp[i][0]必须用dp[i-1][1]而不是-prices[i]——因为今天买入时可能已经交易过好几轮了。有人会疑惑既然允许无数次买卖那122题不是可以用贪心累加所有正差吗确实可以而且代码更短public int maxProfit(int[] prices) { int ans 0; for (int i 1; i prices.length; i) { ans Math.max(0, prices[i] - prices[i-1]); } return ans; }但我要提醒一句贪心解法只适用于“不限制交易次数且没有冷冻期/手续费”的场景。一旦限制次数或加冷冻期这个贪心立刻失效。所以训练营里老师强调“122题的贪心可以用但DP必须会”本质是让你把状态机模型练熟为123题铺路。3.3 这题的易错点写代码时滚动变量的更新顺序122题用滚动数组时很多新手会写出这么一段翻车代码hold Math.max(hold, cash - prices[i]); cash Math.max(cash, hold prices[i]);问题在于第二行里的hold已经是今天更新后的hold了而cash的转移应该基于昨天的hold。万一今天的hold因为买入变得更小而cash的更新又使用了这个更小的hold结果就会出现“先用新hold计算卖出利润”的逻辑错误。正确做法是先保存昨天状态或者把两行的顺序反过来。prevHold hold; hold Math.max(hold, cash - prices[i]); cash Math.max(cash, prevHold prices[i]);这个坑看似不起眼但在188题和309题写多维滚动数组时同样的错误会造成答案偏小或偏大的问题而且很难排查。4. 123题状态从两个变成四个交易次数成了第二维度4.1 为什么两个状态不够用到了123题“最多买卖两次”意味着同一时刻可能有以下四种状态第一次买入后持有第一支第一次卖出后已经卖了一次空仓第二次买入后持有第二支第二次卖出后已经卖完两次空仓如果仍然只用“持有/不持有”两个状态就无法区分“不持有但还没买过”和“不持有但已经卖过一次”。因为这两种不持有状态下下一次买入的成本基础是不同的——前者是0利润开始第一次买后者要基于第一次卖出的利润开始第二次买。所以必须把状态扩展成四个这也是动态规划处理约束的通用手段给状态机增加“记忆”维度。4.2 四状态递推公式定义dp[i][0]第一次持有dp[i][1]第一次不持有已经卖过一次dp[i][2]第二次持有dp[i][3]第二次不持有已经卖完两次初始化dp[0][0] -prices[0] dp[0][1] 0 dp[0][2] -prices[0] // 同一天买入第二次实际是“先卖后买”利润仍为-prices[0] dp[0][3] 0递推dp[i][0] max(dp[i-1][0], -prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]) dp[i][2] max(dp[i-1][2], dp[i-1][1] - prices[i]) dp[i][3] max(dp[i-1][3], dp[i-1][2] prices[i])翻译成人话就是第一次持有要么继续持有第一支要么在今天第一次买入第一次卖出要么继续保持卖过一次的状态要么在今天把第一支卖出第二次持有要么继续持有第二支要么在已经卖过一次的基础上今天买入第二支第二次卖出要么保持卖完两次的状态要么在今天卖出第二支4.3 两个容易让人懵的地方第一dp[0][2]为什么初始化为-prices[0]而不是某个负无穷因为题目允许“同一天先卖后买”虽然这看起来像两次操作但实际利润等价于没有操作。所以把第二天的初始持有成本直接当作-prices[0]是可行的而且这样递推下去不会错。如果设成负无穷反而需要额外的边界判断。第二dp[i][2]为什么不能从dp[i-1][0]直接转移过来因为从“第一次持有”直接变成“第二次持有”意味着同一时刻持有两支股票这在题目里是不允许的。正确路径必须先经历dp[i-1][1]第一次卖出再通过买入到达第二次持有。4.4 代码实现public int maxProfit(int[] prices) { int firstBuy -prices[0]; int firstSell 0; int secondBuy -prices[0]; int secondSell 0; for (int i 1; i prices.length; i) { firstBuy Math.max(firstBuy, -prices[i]); firstSell Math.max(firstSell, firstBuy prices[i]); secondBuy Math.max(secondBuy, firstSell - prices[i]); secondSell Math.max(secondSell, secondBuy prices[i]); } return secondSell; }这里需要再次强调第一行的firstBuy更新后第二行firstSell使用的firstBuy必须是更新后的值这在逻辑上是正确的因为“今天卖出”要基于“今天买入”后的结果虽然从直觉上“买入再卖出”没有意义但在公式层面是自洽的。唯一需要小心的是secondBuy和secondSell的顺序secondSell必须依赖更新后的secondBuy因为它表示“今天买入第二支后今天卖出”虽然实际中不会这么做但套公式计算出的结果不会超过真实最大值。我实测过各种边界情况全跌序列、全涨序列、先涨后跌再涨、一直横盘四状态滚动版本的结果都和二维数组版本的答案完全一致。这套代码写熟之后直接套到188题几乎没有成本。5. 188题把“两次”泛化成“k次”核心是维度抽象5.1 从4个状态到2k个状态188题把123的“最多两次”换成了“最多k次”。如果还是手动枚举状态那要写2k个变量显然不现实。必须把“交易次数”变成数组的维度。定义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] prices[i]) dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])解释卖出股票时已完成次数从j保持不变因为卖出前已经是第j次交易中买入股票时买入前必须已经完成j-1次完整交易买入后才进入第j次交易。5.2 边界条件与k值剪枝初始化时dp[0][j][1]应该视为-prices[0]还是负无穷严格来说第0天完成0次交易后买入持有状态是合法的但完成1次以上交易后再持有不可能发生在第0天。所以dp[0][0][1] -prices[0]其他j 0的持有状态设为极小值如Integer.MIN_VALUE。另一个关键点是k的剪枝如果k prices.length / 2那上限已经没有约束力等价于无限次交易可以退化成122题的贪心。为什么是n/2因为一次完整交易至少需要两天先买后卖所以n天之内最多完成n/2次交易。k超过这个值直接当作无限次处理避免开过大的数组。5.3 代码实现与空间压缩public int maxProfit(int k, int[] prices) { if (prices.length 0 || k 0) return 0; if (k prices.length / 2) { int ans 0; for (int i 1; i prices.length; i) { if (prices[i] prices[i-1]) ans prices[i] - prices[i-1]; } return ans; } int[][] dp new int[k1][2]; for (int j 0; j k; j) { dp[j][0] 0; dp[j][1] Integer.MIN_VALUE; } for (int price : prices) { for (int j k; j 1; j--) { dp[j][0] Math.max(dp[j][0], dp[j][1] price); dp[j][1] Math.max(dp[j][1], dp[j-1][0] - price); } } return dp[k][0]; }这里有个细节我从训练营同学那里学到后实测有效内层循环j从大到小遍历是为了保证在更新dp[j][1]时dp[j-1][0]还是“昨天”的值而不是“今天”刚更新的值。如果从小到大遍历dp[j-1][0]可能已经被今天的卖出逻辑更新导致买入的利润基数偏大。在188题上我见过最多的错误是初始化问题很多人把dp[j][1]全部初始化为-prices[0]这在高k值场景下会干扰答案。严格来说只有dp[0][1]完成0次交易但持有股票在第一天合法但实操中把所有dp[j][1]都设为Integer.MIN_VALUE再用Math.max递推效果等价且更安全。6. 309题冷冻期不是新机制而是对“买入边”加了限制6.1 状态从“持有/不持有”变成“持有/不持有且可买/不持有且冷静”309题加了一个规则卖出后的第二天不能买入必须等一天。表面上看是“加了一天限制”实际上迫使我们把“不持有”状态拆成两种第i天不持有股票且不是因为当天卖出即第i1天可以买入第i天不持有股票且是因为当天卖出即第i1天处于冷冻期不能买入于是三状态定义dp[i][0]第i天结束后持有股票 dp[i][1]第i天结束后不持有股票且不处于冷冻期明天可以买 dp[i][2]第i天结束后不持有股票且处于冷冻期明天不能买6.2 递推公式dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][2]) dp[i][2] dp[i-1][0] prices[i]逐条解释持有股票要么继续持有要么从“可买的不持有状态”买入。注意不能从冷冻期买入。不持有且可买要么昨天就不持有且可买今天继续观望要么昨天是冷冻期今天冷冻期结束变成可买状态。注意这里不能从冷冻期状态再转移到可买因为冷冻期转移的来源是“昨天卖了”昨天的卖出利润通过dp[i][2]已经在昨天结算今天只是解冻。不持有且冷冻只有一种来源就是今天卖出所以直接等于昨天持有今天的卖出价。6.3 什么时候买入、什么时候卖出才最优拿一个具体例子走一遍会清晰很多比如prices [1,2,3,0,2]。分析第3天价格0的情况如果没有冷冻期理想策略是第2天卖出3后第3天买入0再第4天卖出2利润是(3-1)(2-0)4但因为有冷冻期第2天卖出后第3天不能买所以实际最优解是第2天不卖第3天卖虽然亏一点或者干脆第3天买入第4天卖出整体利润反而不同。这就是冷冻期对“买入时机”的约束如何改变最优策略。滚动数组版本public int maxProfit(int[] prices) { int hold -prices[0]; int noHoldNoFrozen 0; int noHoldFrozen 0; for (int i 1; i prices.length; i) { int prevHold hold; int prevNoHoldNoFrozen noHoldNoFrozen; int prevNoHoldFrozen noHoldFrozen; hold Math.max(prevHold, prevNoHoldNoFrozen - prices[i]); noHoldNoFrozen Math.max(prevNoHoldNoFrozen, prevNoHoldFrozen); noHoldFrozen prevHold prices[i]; } return Math.max(noHoldNoFrozen, noHoldFrozen); }这题的常见坑发生在noHoldNoFrozen的更新上有人会把它写成Math.max(prevNoHoldNoFrozen, prevHold)这是错的——因为“持有状态下直接变成不持有且可买”只可能通过卖出实现而卖出当天应该处于冷冻期。如果直接从hold转移到noHoldNoFrozen相当于抹掉了冷冻期让第二天可以继续买入违反了题目规则。7. 把五道题串起来之后我再分享几个实战翻车点刷完这组题我最大的收益不是记住某个公式而是彻底理解了“状态机DP”的通用套路先画状态图标出每条转移边的条件和动作再定义状态数组最后写递推公式。121是2个状态2条边122保持2个状态但有买入受到“昨天空仓”约束的边123扩展到4个状态188把状态数量参数化309则新增一条冷链。每道题的差异都落在了状态图上的某条边。下面这几个坑是我自己也踩过、以及在训练营刷题群里看到别人反复踩的单独列出来提个醒。7.1 初始化时负无穷的使用时机如果是“最多k次交易”数组里必须区分“不可能状态”和“合法但利润为负”的状态。Integer.MIN_VALUE应该只用于不可能的状态不能给-prices[0]这种可能状态用。否则两个极小值相加直接溢出成正数答案必然错误。这里有一个非常隐蔽的问题当Integer.MIN_VALUE prices[i]时Java中会发生溢出变成正数导致本该不可达的状态变得“可达”最终答案偏大。我见过的解法里有人用Integer.MIN_VALUE / 2有人用-1000000000目的都是防止溢出。我个人更推荐在写188题时给dp[j][1]设成-0x3f3f3f3f这类足够小但不作相加的常数或者在公式里加判断避开极小值运算。7.2 滚动数组的更新顺序只要你写空间压缩版本就必须想清楚“更新时用到的是昨天的值还是今天已经更新的值”。121和122因为只有两个变量比较简单123有四个变量很容易乱188题如果内层循环顺序写错递推结果会变成“同一天内多次买卖”这虽然在无冷冻期时不至于超过真实答案因为有约束但会让代码逻辑混乱难以调试。我建议初学阶段先写二维数组版本跑通后再压缩空间不要一上来就写滚动数组。7.3 理解“完成交易次数”的语义188题里dp[i][j][1]表示“已经完成j次交易当前持有”这个状态初学时容易混淆当前正在第j1次交易中为什么说完成了j次因为这个状态是“准备买第j1次或已经买了但没卖”一旦卖出才计入第j1次。把“持有”理解为“一次交易进行中”次数维度只记录“已经结束的交易数”整个递推就顺了。如果你在dp[i][j][1]的更新时写dp[i-1][j-1][0] - prices[i]那就错了因为买入本身不会增加已完成交易次数。7.4 冷冻期题目中“卖出当天”到底处于什么状态309题最容易混淆的点是卖出当天到底算是冷冻期第1天还是算“不持有且可买”从定义中可以看到我把它归为“不持有且冷冻”状态表示明天不能买。实际应用中如果卖出后当天又涨你不可能再买因为同一笔钱只能买一次所以无论叫“冷冻”还是“不可买”含义是一致的。关键是第二天必须通过noHoldNoFrozen max(prevNoHoldNoFrozen, prevNoHoldFrozen)这个式子解冻并且当天不能买入。7.5 这些题的共性测试用例我刷这类题时固定用三组用例来验证代码空数组或单元素数组所有方法应该返回0严格递增序列比如[1,2,3,4,5]一次买卖、无限次买卖、k次买卖的结果应该一致除了k0先涨后跌再涨比如[3,3,5,0,0,3,1,4]这是力扣123的官方示例专门用于测“两次买卖”的正确性如果用我上面的滚动数组代码跑这三组用例121能返回最大值122能拿到所有正差之和123和188在k2时应该得到6第3天买第4天卖赚3第5天买第8天卖再赚2加1309在给定示例里应该得到3。如果结果对不上优先检查初始化和循环顺序而不是递推公式本身——公式如果错了通常所有用例都会错而不仅仅是边界出错。刷完这五道题再把题目顺序打乱重做一遍每道题都先自己画状态转移图再写代码会发现自己对动态规划的理解上了一层楼。这个过程比刷十道重复题型都管用——因为股票系列最大的价值就是让你看清“同一个状态机模型如何在不同约束条件下变化”这也是算法面试里最常考的一种能力。