动态规划股票买卖：121/122/123题状态转移全解析

1. 三道题是什么为什么值得串起来刷1.1 从题目描述看递进关系121题“买卖股票的最佳时机”是股票系列的开胃菜要求整个生命周期只能买卖一次买入之后才能卖出不能在卖出之前先赚差价。这个约束看着简单细想会发现很多门道你是先面对价格一步步变化不知道明天是涨是跌只能在做决策时保证“当前持有状态”是合法的。122题把限制放宽成可以无限次交易只要手里最多持有一股今天卖了可以再买买了只要不卖就行。123题又加回一个上限最多完成两笔交易。三题的输入都是同一个价格数组变的只是交易次数约束所以解法天然适合用同一套动态规划主线推下去。我把这三道题放在一起刷还有一个现实原因它们是代码随想录算法训练营第41天的打卡内容也是动态规划股票系列的入门三板斧。很多刷题的人一上来就背“状态转移方程”但为什么状态是持有和不持有、为什么买入时现金是负数、为什么第三次交易的买入要用上一次卖出的余额这些点如果不串起来想遇到变种题很容易翻车。1.2 学习目标和前置知识刷完这三题你至少应该掌握三件事第一能给任意一道股票题写出带状态含义的DP数组而不是靠背第二能说清楚“交易次数”这个约束通过什么方式体现在状态数量和初始化里第三能区分哪些题目可以用贪心哪些必须用DP以及贪心为什么在某些题里失效。前置知识只需要基础的动态规划概念。如果你会用一维数组做爬楼梯、斐波那契再看这三道题就够用了。你不需要一开始就把所有股票变种都刷完先把这边的状态模型建好后面188题、309题、714题会顺很多。2. 121题一次买卖先讲清楚DP的“持有/不持有”状态2.1 暴力思路为什么不行先看最直白的解法枚举买入日 i 和卖出日 j要求 j i计算 prices[j] - prices[i] 的最大值。这个双重循环的时间复杂度是 O(n^2)当数组长度上到十万就直接超时。还有一些人会做一层优化把 prices 数组转成相邻两天的差值再用最大子数组和来做复杂度能降到 O(n)但思考路径完全绕进了另一个模型对后面的122、123没有帮助。问题的核心在于暴力枚举只关心“在哪天买、在哪天卖”没有把“当前手里有没有股票”这个约束写进流程。而股票问题的所有变种本质都在处理这个持有状态能不能买、能不能卖、能交易几次。所以从DP入手一上来就建状态虽然第一题看起来有点杀鸡用牛刀但对后续题目是连续的投资。2.2 动态规划状态定义与递推推导用 dp[i][0] 表示第 i 天交易结束后手里还持有股票时的最大现金dp[i][1] 表示第 i 天交易结束后手里没有股票时的最大现金。这里的“现金”你可以理解成账面上的余额买入要花钱余额减少卖出会收钱余额增加。我们最终期望余额最大等于净利润最大。先看 dp[i][0]。第 i 天结束后手里有股票有两种情况要么第 i-1 天就已经持有今天什么都不做即 dp[i-1][0]要么今天刚买入由于只能买卖一次买入前没有累积利润所以买入后现金是 0 - prices[i]写成 -prices[i]。两者取最大dp[i][0] max(dp[i-1][0], -prices[i])再看 dp[i][1]。第 i 天结束后手里没有股票也有两种情况要么第 i-1 天就没有今天什么都不做即 dp[i-1][1]要么第 i-1 天持有今天卖出到账现金变成 dp[i-1][0] prices[i]。两者取最大dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])你可能会困惑为什么 dp[i][0] 的第二项不需要 dp[i-1][1] 参与因为“今天买入”这个操作的前置条件是“买入前不持股”而这里只能交易一次买入前就是没有股票、没有利润的初始状态所以现金起点恒为0。这也是121和122唯一的本质差别所在。2.3 初始化、遍历顺序和代码实现初始化时第0天买入现金是 -prices[0]即 dp[0][0] -prices[0]第0天不买现金是0即 dp[0][1] 0。遍历顺序就是从左到右从第1天到第n-1天因为每一天只依赖前一天的状态顺着推即可。完整代码如下public int maxProfit(int[] prices) { int n prices.length; int[][] dp new int[n][2]; // 第0天手里有股票说明买入了 dp[0][0] -prices[0]; // 第0天手里没股票说明没买入 dp[0][1] 0; for (int i 1; i n; i) { dp[i][0] Math.max(dp[i - 1][0], -prices[i]); dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i]); } return dp[n - 1][1]; }如果觉得二维数组占了多余空间还可以压缩成两个变量滚动更新。这里有个细节不要在同一步里用更新完的 hold 去算 empty否则会引入同一天的错误状态。更稳妥的写法是先用临时变量把新旧状态隔开public int maxProfit(int[] prices) { int hold -prices[0]; int empty 0; for (int i 1; i prices.length; i) { int nextHold Math.max(hold, -prices[i]); int nextEmpty Math.max(empty, hold prices[i]); hold nextHold; empty nextEmpty; } return empty; }这里最需要想明白的一点是最终答案为什么返回 empty 而不是 max(hold, empty)因为交易结束后手里还持股没有意义必须卖出去才落袋为安。就算 prices 一路下跌你也可以选择第0天不买empty 保持0不会出现负数答案。2.4 一个更简单的贪心写法以及和DP的区别121其实还有更短的O(n)贪心遍历 prices记录历史最低价 minPrice同时用当前价格减去历史最低价更新答案。代码几行就能写完因为“只能买卖一次”等价于“找一组 i j使 prices[j] - prices[i] 最大”贪心一次遍历就够。那是不是可以跳过DP只背贪心我的建议是不要。121的贪心之所以成立是因为交易次数限制为1局部最优就是全局最优到了123题“最多两笔”贪心很难处理“分两段赚钱”的边界容易陷入局部。所以这组题的正确打开方式是121用DP建立状态模型贪心作为辅助理解122和123在同一个DP框架内扩展。提示如果你在刷题时时间很紧至少要保证121和123是真正弄懂的。122是中间过渡题把握好买入状态的差异就能秒杀。3. 122题无限次交易把买入的“起点”换掉3.1 和121题唯一的区别在哪122题允许无限次交易但任何时刻手里最多持有一股。这个限制和DP模型几乎无缝衔接第 i 天结束后持有股票要么昨天就持有今天没动要么今天买入。唯一的变化是今天买入时手里的现金不再是无脑从0开始而是用“昨天不持股时的最大现金”减去今天的价格也就是 dp[i-1][1] - prices[i]。所以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买入之前是“初始现金0”122买入之前是“之前交易攒下的利润”。这就是两道题在公式上的全部分歧。如果你在代码里把122误写成 0 - prices[i]等于偷偷把交易次数限制回一次这是很多人一上来写混的根源。3.2 为什么贪心也能做而且做起来更简单122用贪心也很快只要 prices[i] prices[i-1]就把 prices[i] - prices[i-1] 累加到答案里。这个做法的正确性可以这样理解在没有交易次数限制时一支股票从10块涨到15块你在15块卖赚5块拆成每天看就是10到12赚2块、12到15赚3块总和还是5块。把所有上涨区间的差值累加不会漏掉任何利润。那为什么我仍然建议你用DP写一遍因为贪心只适用于“次数不限制”的场景一旦题目变成“最多两笔”“含手续费”“含冷冻期”贪心的局部最优叠加就会失效。以122为过渡掌握DP版买入现金的变化对后续变种题收益更大。3.3 完整代码与压缩写法二维DP版本的完整代码public int maxProfit(int[] prices) { int n prices.length; int[][] dp new int[n][2]; dp[0][0] -prices[0]; dp[0][1] 0; for (int i 1; i n; i) { dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i]); } return dp[n - 1][1]; }压缩变量版public int maxProfit(int[] prices) { int hold -prices[0]; int empty 0; for (int i 1; i prices.length; i) { int nextHold Math.max(hold, empty - prices[i]); int nextEmpty Math.max(empty, hold prices[i]); hold nextHold; empty nextEmpty; } return empty; }对比121的压缩代码你会发现只有 nextHold 那一行把 -prices[i] 换成了 empty - prices[i]。这个微小差异就是“一次交易”和“无限次交易”的分水岭。刷题时养成对比代码的习惯比单纯背题解要有效得多。4. 123题最多两笔交易状态数翻倍也分得清4.1 5个状态到底是怎么来的122的问题是“不限次数”123的问题是“只限两笔”。交易次数一限持有/不持有的两状态就不够用了因为“不持有”这个描述掩盖了你是“一次都没卖过”还是“已经完成过第一笔卖出”。这两种情况在后一次买入时能用的现金完全不同。我把123题的状态按“操作进度”拆成5个状态0还没进行任何交易无操作状态1已经发生了第一次买入手里持有股票状态2已经完成了第一次卖出手里没有股票状态3已经发生了第二次买入手里持有股票状态4已经完成了第二次卖出手里没有股票。注意这里写的是“当天交易结束后”的状态。为什么是5个而不是4个一笔交易包含买入和卖出两个动作两笔交易就是4个动作再加上最开始什么都还没做的“无操作”正好5个。4.2 状态转移逐行推导状态0恒为0不需要参与最大值比较因为没有任何动作能让“无操作状态”变成其他数值它也不会从其他状态转移过来。第一次买入即状态1。要么昨天已经是第一次买入后的持有状态今天什么也不做即 dp[i-1][1]要么昨天是状态0今天买入现金变成 dp[i-1][0] - prices[i] -prices[i]。于是dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])第一次卖出即状态2。要么昨天已经完成第一次卖出今天没动作即 dp[i-1][2]要么昨天是第一次持有状态今天卖出现金变成 dp[i-1][1] prices[i]。于是dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i])第二次买入即状态3。买入的现金来自第一次卖出后的余额所以要从状态2转移而来再减去今天的价格dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i])第二次卖出即状态4。从状态3持有股票的状态卖出现金增加dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i])这四行转移里最容易写错的是 dp[i][3] 的转移来源。很多人会顺手写成 dp[i-1][1] - prices[i]逻辑上等于第二次买入时只用了“第一次买入后”的余额完全绕过了第一次卖出状态含义就乱了。记住第二次买入之前必须先完成第一次卖出所以它只能从状态2转移过来。4.3 初始化和最终取值的两个坑初始化有一个经典坑dp[0][1] 和 dp[0][3] 都要设置成 -prices[0]。dp[0][1] 好理解第0天第一次买入。dp[0][3] 为什么也要设成 -prices[0]因为递推需要给第二次买入一个起点最合理的做法是假设第0天完成了一次买入、又完成了一次卖出账面相等然后立即进行第二次买入。这样现金同样是 -prices[0]。如果不设置这个值第二次买入的转移会从0开始减算出来的收益虚高。最终答案为什么取 dp[n-1][4]题目说“最多两笔”如果只做一笔或不做会不会漏不会。状态4的转移链路依赖状态3状态3又依赖状态2状态2又依赖状态1整条链是通的。当某一段利润为负时Math.max 会自动选择“不交易”的路径。所以 dp[n-1][4] 天然覆盖了做零笔、做一笔、做两笔三种情况下的最大值。完整代码public int maxProfit(int[] prices) { int n prices.length; int[][] dp new int[n][5]; // 第0天第一次买入 dp[0][1] -prices[0]; // 第0天第二次买入的起点同样设为 -prices[0] dp[0][3] -prices[0]; for (int i 1; i n; i) { dp[i][0] dp[i - 1][0]; dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); dp[i][2] Math.max(dp[i - 1][2], dp[i - 1][1] prices[i]); dp[i][3] Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]); dp[i][4] Math.max(dp[i - 1][4], dp[i - 1][3] prices[i]); } return dp[n - 1][4]; }4.4 一维数组压缩写法二维数组版本足够清晰但为了面试手写快一点我也建议掌握压缩变量版。用4个变量分别表示第一次买入后、第一次卖出后、第二次买入后、第二次卖出后的最大现金public int maxProfit(int[] prices) { int buy1 -prices[0], sell1 0; int buy2 -prices[0], sell2 0; for (int i 1; i prices.length; i) { buy1 Math.max(buy1, -prices[i]); sell1 Math.max(sell1, buy1 prices[i]); buy2 Math.max(buy2, sell1 - prices[i]); sell2 Math.max(sell2, buy2 prices[i]); } return sell2; }这里最要紧的是更新顺序必须按 buy1、sell1、buy2、sell2 依次更新不能打乱。因为 buy2 要使用同一个价格上刚更新完的 sell1如果先更新 buy2它读到的 sell1 还是上一个价格的状态结果就会偏差。这是压缩写法里最隐蔽的坑没有之一。5. 三题对比、扩展与面试应用5.1 用一张表看三题的状态差异我把三道题的核心差异整理成一张表刷题时对照这张表复习效率会高很多题目交易次数DP状态维度买入现金来源能否贪心1211次2个状态0 - prices[i]可以122无限次2个状态dp[i-1][1] - prices[i]可以123最多2次5个状态上一次卖出后的余额不可以直接贪心看完这张表你会发现三个题真正的差异只有两个维度状态个数以及买入现金从哪来。只要把这两个问题想明白股票系列的主干就算吃透了。5.2 从123到188任意K次交易的通用化188题把“最多两笔”改成“最多K笔”。套路是完全一样的只不过状态个数扩展成 2K1 个其中奇数下标表示第 k 次买入后的持有状态偶数下标表示第 k 次卖出后的不持有状态下标0还是初始无操作。代码只需要在123的基础上套一层内层循环按交易次数枚举状态。所以123的价值不只是目前这三道题的终点它是通往“任意次数”题目的桥梁。如果你把123的转移亲手推导一遍再看188题会觉得熟门熟路。5.3 面试中怎么答这类题面试官考股票题时通常期待候选人做到三步先解释状态定义再推导转移方程最后分析时间空间复杂度。很多人一上来就埋头写代码状态含义还没说清楚容易让面试官怀疑是不是背的。我建议你先找个小例子比如 prices [3,3,5,0,0,3,1,4]在草稿纸上手推一遍 dp 数组然后对着状态表讲思路。这样既证明你真的理解DP也方便后续面试官追问“如果把两笔改成K笔怎么做”你可以顺着状态扩展思路现场答出来。时间复杂度和空间复杂度也没什么悬念三题都是 O(n) 时间和 O(n) 空间压缩变量后可以降到 O(1) 空间这是加分项。6. 打卡实操心得我刷这三题的几个建议6.1 先画状态转移表再写代码刷这三题时我最推荐的路径不是先看题解再抄代码而是先在纸上画一张状态转移表。列是“状态”行是“天数”每格填 dp 值。拿 prices [7,1,5,3,6,4] 为例把121的四个关键格填完你立刻能看出持有状态在价格低点被更新、不持有状态贴着最大利润增长。这个动手过程比盯着屏幕看十遍公式管用得多。到了123题不过是从两列变成五列画表的时间成本变高但收益也更明显状态怎么互相依赖、哪里容易漏初始化全都暴露在表格里。6.2 打表诊断问题代码跑不对时别对着公式冥思苦想直接打印 dp 数组。打印之后找第一处和手推结果不一样的格子问题基本就定位了。根据我刷题的经验最常见的是三种bug123题漏初始化 dp[0][3]第二次买入的转移写成了 dp[i-1][1] - prices[i]压缩变量版本更新顺序颠倒。这三个问题靠肉眼盯公式很难发现打表之后一目了然。尤其是压缩写法我建议初学阶段先写二维数组确认逻辑无误后再改成压缩版。6.3 二刷验证的方法第一遍刷完隔几天可以用压缩变量版重写一遍这是检验是否真懂的好标准。如果还能一次写对说明状态定义和转移关系已经内化。另一个建议是把188、309、714这三题安排在差不多的周期里一起刷。它们用的核心状态模型和121、122、123完全一致区别只是额外条件不同比如K次限制、冷冻期、手续费。串在一起刷你会发现所有股票题共用一套思考框架单题重复刷反而容易陷入记忆题解的误区。最后再分享一个小技巧无论刷到哪道股票题都先在题目旁边写清楚“交易次数限制是什么”“买入现金从哪里来”这两行字再开始设计状态。这两行想清楚代码怎么写都不会偏。