企业官网建设流程全解析

股票买卖系列：从一次交易到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*K+1个状态。偶数下标0,2,4,...,2K表示“不持有且已卖出x次”，奇数下标1,3,5,...,2K-1表示“持有且已买入x+1次”。

用一个二维数组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*K+1): 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题为例，如果只用一个长度为2K+1的数组，在遍历状态时必须从后往前更新，否则本轮刚更新的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 常见问题速查表

4.4 刷题节奏与巩固建议

代码随想录安排三天刷五道股票题是有讲究的，不建议一天全刷完。第一天吃透121和122，把二维DP写熟；第二天做123，并用123的“五状态”反推188的通用写法；第三天做309，重点体会“约束条件如何改变状态拓扑”。每天刷完后，用“不看你笔记”的方式默写一遍转移方程，这是测试自己是否真正理解的最佳方法。

另外，大部分人在刷完这五道题后，都会形成一种“条件反射”：任何看起来像“买卖、持有、冷却”的题目，第一反应就是状态机。这是一种好现象，但也要注意不要过度泛化。最后我想说一个实战小心得：面试时遇到股票系列变体题，不要急着写代码，先花一分钟把题目里的约束条件往“状态+行为”的框架里套一遍，看看多出的约束是增加了状态数量，还是减少了某些转移路径。想清楚这个问题，代码基本就是顺水推舟的事。

我刷完这个系列的最大体会是，动态规划不是“背方程”，而是“搭框架”。你今天多理解一分状态转移的来龙去脉，以后遇到再复杂的DP题，底层思路都是通的。如果你正在训练营里跟这个节奏，踏踏实实把每一道题的转移方程推导一遍，收益远比直接看答案大得多。