股票买卖系列从一次交易到K次交易的动态规划递进之路如果你刷LeetCode刷到中后期一定会发现有一类题目像“套娃”一样——买卖股票的最佳时机I到IV再加个冷冻期版本难度依次递进解法却又高度相似。代码随想录算法训练营第四十九到五十一天就集中安排了这五道题121、122、123、188和309。这五道题刷透了动态规划里“状态机”这一类问题基本就能拿捏住。这五道题的核心不是让你记住五个不同的转移方程而是让你理解同一个状态机模型如何在不同约束下演进。121是最基础的“一次交易”122放开了次数限制123和188分别限定两次和K次309又加入了“卖完后必须冷却一天”的特殊规则。每加一个约束DP数组的维度或者状态的数量就变一次但底层逻辑是连贯的。所以这个系列非常适合用来训练“从一道题推广到一类题”的能力这也是算法训练营把它连续安排三天的原因。这篇文章我会把这五道题放在一起拆重点讲状态怎么定义、转移方程为什么这么写、边界条件有什么坑以及空间优化时的注意事项。我尽量用“一个模型套所有题”的方式来讲而不是每道题目孤立地贴一遍代码。适合正在刷动态规划、被股票系列绕晕的同学也适合准备面试前想快速把这类题体系化复习的人。1. 整体思路为什么股票系列是动态规划最佳练习场1.1 从“直觉解法”到“状态机思维”的转变很多人刚开始刷121题时第一反应是暴力法——两层循环枚举所有买入卖出时机记录最大差值。这个方法很好理解但遇到122题“限制改为可以多次交易”时暴力法就彻底失灵了因为你根本不知道要枚举多少组买卖。这时候就得换思路。动态规划的核心不是去模拟“哪天买、哪天卖”而是把每一天结束时的状态抽象出来再根据当天发生的行为买、卖、不操作来更新状态。股票系列题目尤其适合这种抽象因为它天然有“持有现金”和“持有股票”两种状态再叠加“交易次数”“冷却期”这些约束状态就多了起来这就是状态机的雏形。我举一个生活化的类比把“持有股票”想象成你在经营一家小店每天打烊后你问自己两个问题——我现在手头有没有囤货如果囤了我是亏着拿着还是干脆清仓第二天开门时你的决策就只取决于这两个答案跟昨天的细节无关。DP的“无后效性”就是这个意思未来的决策只依赖当前状态不依赖你怎么走到这个状态的。1.2 五道题目的递进关系图这个系列的关系我梳理成一条线121只能买卖一次就是“穷小伙”版本状态最少。122不限次数每次操作独立转移方程的写法开始有变化。123最多两次中间要经历一个“第一次卖完再买第二次”的阶段。188把两次推广到K次维度从常量变成变量。309在122基础上加了冷冻期转移路径少了一条。本质上它们共用一套框架每一天的DP值 上一天的状态 当天的行为收益。唯一不同的是你多记录了一个维度的信息——交易了几次、或者昨天是否刚卖出。我刷完这几道题的最大感受是一旦你在121里把dp[i][0]和dp[i][1]的含义彻底搞清楚后面每道题只是在这个基础上加状态不要把每道题当成新题目来记。所以这篇文章也会按这个递进逻辑往下走。先讲121的基础状态机再一步步加约束把188和309作为“综合应用题”来分析。2. 核心解题框架先吃透121和122这两个基石2.1 121题的状态定义与转移方程拆解121题的要求是只能买卖一次求最大利润。用二维DP数组dp[i][0]表示第i天结束后手里不持有股票时拥有的现金dp[i][1]表示第i天结束后手里持有一股股票时拥有的现金。注意这里的“现金”是一种虚拟值初始持有本金为0买入股票会让现金变成负数卖出后加上当前股价。转移方程如下dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) dp[i][1] max(dp[i-1][1], -prices[i])第一个方程说“今天不持有”可以来自两种情况昨天不持有今天也不操作或者昨天持有今天卖掉。第二个方程说“今天持有”也可以来自两种情况昨天持有继续拿着或者今天刚买入。关键在第二行的-prices[i]它隐含了“只能买一次”的约束——如果你今天买入那就是生命中唯一的一次买入所以直接把现金置为负的股价不需要考虑之前是否买过。这里有一个值得深挖的细节为什么dp[i][1]的买入分支不是dp[i-1][0] - prices[i]因为dp[i-1][0]在“只能买卖一次”的约束下如果它之前已经卖出过一次股票那现金可能大于0再拿它去买入就会导致“买第二次”的语义。而121只允许一次交易所以买入分支必须强制从0本金开始即-prices[i]。这个细节在刚开始刷时最容易忽略我也是在这个地方卡过很久。一旦理解了这里后面122的“可以多次交易”就只是把这一行改成dp[i-1][0] - prices[i]而已。注意边界条件是dp[0][0] 0第0天不持有什么都没做dp[0][1] -prices[0]第0天买入现金变成负的。这个初始化也是很多人的坑后面统一说。2.2 122题的变化交易次数不再受限后的转移差异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第二行从-prices[i]变成了dp[i-1][0] - prices[i]。这个改动背后的逻辑是因为可以多次交易你手上可能已经有多次买卖积累的现金dp[i-1][0]今天买入新股票应该是用这些现金去买而不是每次都假设从0本金开始。很多教程会把122跟“贪心算法”放在一起讲因为从纯收益角度看122的最大利润等价于把所有上涨段的差值加起来——相邻两天如果涨价就赚差价。这个结论对简化计算很有用但如果你想真正理解DP的递进思路还是建议老老实实把状态转移方程写一遍因为123和188不能用贪心只能用DP。我在实际刷题中有一个体会122题表面是在“放宽限制”实际上是在教我们一个非常重要的建模思想——当“行为”可以重复发生时状态转移方程中的买入分支必须显式引用“前一天的现金状态”而不是写死一个常量。这个思想会沿用一辈子。3. 实操环节从两次交易到K次交易的代码递进3.1 123题两次交易的五状态推导到了123题“最多完成两笔交易”引入了一个新维度交易次数。最直观的做法是加一个维度k表示截止当天已经完成的交易笔数但还有一个更巧妙的做法也是代码随想录里主推的直接把状态拆成五个。五个状态分别是dp[i][0]没有进行任何交易dp[i][1]第一次持有股票dp[i][2]第一次不持有已卖出一次dp[i][3]第二次持有股票dp[i][4]第二次不持有已卖出两次转移方程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]) dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i])你注意到没有这五个状态本质上就是“121的两个状态”做了两次串联第一次买入卖出对应dp[i][1]和dp[i][2]第二次买入卖出对应dp[i][3]和dp[i][4]中间的桥梁是dp[i][2]——第一次卖完后的现金状态。初始化时dp[0][1] -prices[0]dp[0][3] -prices[0]。这里有一个新手最容易懵的地方为什么第二次买入的初始值也是-prices[0]原因是在第0天你可以认为第一次买入卖出已经完成且收益为0即dp[0][2] 0然后再买入第二次所以现金是0 - prices[0] -prices[0]。隐含的意思是“同一天可以完成第一次的买和卖再买第二次”这虽然在实际炒股中不可能但DP建模时允许这种操作因为它产生的利润和真实操作没有差别。3.2 188题把两次升维到K次188题是123的一般化最多完成K笔交易。如果你理解了123的“五个状态”188就是把这五个状态扩展到2*K1个状态。偶数下标0,2,4,...,2K表示“不持有且已卖出x次”奇数下标1,3,5,...,2K-1表示“持有且已买入x1次”。用一个二维数组dp[i][j]其中j的范围是0到2K转移方程统一为for i in range(1, n): dp[i][0] dp[i-1][0] for j in range(1, 2*K1): if j % 2 1: # 持有状态买入 dp[i][j] max(dp[i-1][j], dp[i-1][j-1] - prices[i]) else: # 不持有状态卖出 dp[i][j] max(dp[i-1][j], dp[i-1][j-1] prices[i])这里的逻辑对称性非常漂亮奇数状态是“买入”需要用上一个状态少一次交易的现金减去价格偶数状态是“卖出”需要用上一个状态多了一支股票加上价格。写代码时用一个循环就能覆盖所有K值这也是“从2到K”的真正升级点。不过这里有一个性能上的坑如果K非常大比如K n/2二维数组的第二个维度会膨胀得很厉害而且很多状态根本用不到。LeetCode给的K值一般不会太大但在面试中如果把K改成一个很大的数你就需要考虑“压缩状态”或提前判断K n/2时等价于122不限制次数。这个边界条件在比赛里经常成为陷阱值得专门标注一下。3.3 309题冷冻期如何改变转移拓扑309题比122多了一条规则卖出股票的第二天不能买入必须等一天。这个约束直接改变了状态转移的拓扑结构因为“持有”状态多了一个来源判断——昨天刚卖出是不行的。常见的处理方式是引入第三个状态也就是把“不持有”拆成两个dp[i][0]表示今天不持有且“明天可以自由买入”也就是今天没有卖出dp[i][1]表示今天不持有且“明天必须冷静”也就是今天刚卖出再加上dp[i][2]表示持有。这样状态之间互相转移的关系就清晰了从“持有”可以移到“今天卖出”即dp[i][1]。从“今天卖出”在次日只能移到“明天可以自由买入”中间隔一天。从“持有”也可以继续持有不操作。从“明天可以自由买入”可以买入新股票也可以继续等待。用代码表示dp[i][0] max(dp[i-1][0], dp[i-1][1]) dp[i][1] dp[i-1][2] prices[i] dp[i][2] max(dp[i-1][2], dp[i-1][0] - prices[i])这里的重点在第一个方程dp[i][0]的来源是“昨天的状态0”或“昨天的状态1”绝不能是“昨天的状态2”因为持有股票在昨天不能直接变成今天可自由买入——必须先卖出而卖出后今天处于状态1。很多人在这个转移上写错把dp[i-1][1]漏掉或者把dp[i-1][2]加进去都会导致答案错乱。我在刷309时犯过一个比较典型的低级错误把dp[i][1]写成了max(dp[i-1][1], dp[i-1][2] prices[i])。表面上看好像多考虑了“昨天就在冷静期今天继续冷静”但实际上冷冻期只有一天不允许连续两天都在冷静期所以不能用max。这里只能用等号直接赋值。这个细节特别容易忽略因为max用顺手了以后看到“递推”就条件反射写max但冷冻期的状态结构决定了它必须强制转移。4. 常见问题与空间优化陷阱4.1 初始化边界条件的合理解释五道题全部栽在初始化上的情况非常常见。以123题为例dp[0][3] -prices[0]这个初始化很多人不理解甚至有人会写成dp[0][3] dp[0][1] - prices[0] -2 * prices[0]这就是把“两次买入”语义理解错了。关键要明确dp[0][3]表示“第0天结束时处于第二次持有股票的状态”这意味着你“认为”第一次交易已经完成了。为了建模方便我们允许在同一天完成第一次买卖收益为0再买入第二次所以现金是0 - prices[0]。这不是真正的“交易”而是一种状态初始化技巧。理解这个“虚拟完成”的概念后面所有复杂DP的边界初始化都不会再出错。4.2 空间压缩从二维到一维的注意事项很多同学刷到后面会追求“高端”写法把二维DP压缩成一维。没问题但压缩时要特别小心状态覆盖顺序。以188题为例如果只用一个长度为2K1的数组在遍历状态时必须从后往前更新否则本轮刚更新的dp[j-1]会被下一轮dp[j]误用等价于“同一天买入又卖出”这是不合理的。for j in range(2*K, 0, -1): if j % 2 1: # 持有 dp[j] max(dp[j], dp[j-1] - prices[i]) else: # 不持有 dp[j] max(dp[j], dp[j-1] prices[i])倒序遍历的核心原理是dp[j]的更新依赖dp[j-1]而dp[j-1]必须在还未被本轮修改时读取。从2K往1走保证每次读取的都是上一轮的旧值。这个技巧不光用于股票系列很多一维DP压缩场景都用得上。在我自己刷题过程中这个地方犯错的概率极高反复踩了三次坑才形成条件反射。4.3 常见问题速查表题目高频报错/疑惑点原因与解法121把买入分支写成dp[i-1][0] - prices[i]忽略了“只能买一次”的约束买入只能从0本金出发122结果比预期大可能允许了同一天先卖后买检查状态更新顺序或转移逻辑123dp[0][3]初始化写成-2*prices[0]把两次交易理解为“必须真发生两次”实际是虚拟完成第一次交易188K很大时内存溢出增加if K n//2: K n//2退化处理等价于不限制次数309状态1写成了max冷冻期只有一天不能连续两天停留在“刚卖出”状态只能等号赋值所有题空间压缩后结果偏大或偏小大概率是顺序问题持有状态从大下标往小下标更新4.4 刷题节奏与巩固建议代码随想录安排三天刷五道股票题是有讲究的不建议一天全刷完。第一天吃透121和122把二维DP写熟第二天做123并用123的“五状态”反推188的通用写法第三天做309重点体会“约束条件如何改变状态拓扑”。每天刷完后用“不看你笔记”的方式默写一遍转移方程这是测试自己是否真正理解的最佳方法。另外大部分人在刷完这五道题后都会形成一种“条件反射”任何看起来像“买卖、持有、冷却”的题目第一反应就是状态机。这是一种好现象但也要注意不要过度泛化。最后我想说一个实战小心得面试时遇到股票系列变体题不要急着写代码先花一分钟把题目里的约束条件往“状态行为”的框架里套一遍看看多出的约束是增加了状态数量还是减少了某些转移路径。想清楚这个问题代码基本就是顺水推舟的事。我刷完这个系列的最大体会是动态规划不是“背方程”而是“搭框架”。你今天多理解一分状态转移的来龙去脉以后遇到再复杂的DP题底层思路都是通的。如果你正在训练营里跟这个节奏踏踏实实把每一道题的转移方程推导一遍收益远比直接看答案大得多。