1. 121题打头阵：为什么买卖时机问题要拆成“持有”和“未持有”两个状态
到了训练营第41天，动态规划的题目难度已经明显上来了。今天这三道题都是股票买卖系列，121是最基础的一次买入一次卖出，122放开了交易次数，123则限制为最多两笔。这三道题放在同一天打卡是有讲究的——它们共用一套状态设计的底层逻辑，难度又是逐级递进的，一道题吃透了，后面两道就是加状态维度的事。
先看121题。题目描述很直白：给定一个数组 prices，prices[i] 表示股票第 i 天的价格，你只能选择某一天买入，并在未来某一个不同的日子卖出，求能拿到的最大利润。
如果没学过动态规划，很多人第一反应是双层循环暴力枚举：外层定买入日，内层定卖出日，维护一个最大差值。这个解法在思路上完全正确，但时间复杂度是 O(n²)，一旦数组长度上到 10^5，基本就超时了。所以必须想更优的做法。
比较直观的优化思路是贪心：遍历数组时，记录历史最低价格 minPrice，同时用当前价格减去 minPrice 得到当天卖出的利润，不断更新最大利润。这个做法只需要一次遍历，时间复杂度 O(n)，代码也就几行：
var maxProfit = function(prices) { let minPrice = Infinity; let maxProfit = 0; for (let price of prices) { minPrice = Math.min(minPrice, price); maxProfit = Math.max(maxProfit, price - minPrice); } return maxProfit; };这个解法本身没问题，但放到今天这个训练序列里看，它的思维价值不如动态规划。为什么？因为贪心解法只能解决“一次买卖”这个特例，一旦题目改成“可以多次买卖”或者“限制最多两笔”，你需要写新的逻辑；而动态规划的状态设计是可以平滑扩展的，这就是代码随想录把三道题放一起的原因。
121题的DP思路是这样的：每一天交易结束后，手里只有两种状态——持有股票，或者不持有股票。所谓“持有”，不一定是当天买的，可能是之前买入后一直没卖；所谓“不持有”，可能是从没买过，也可能是已经卖出了。我们把状态定义清楚：
- dp[i][0] 表示第 i 天结束后，手里持有一支股票时，账户里的最大现金余额。
- dp[i][1] 表示第 i 天结束后，手里不持有股票时，账户里的最大现金余额。
这里有个初学者容易绕晕的点：为什么用“现金余额”而不是“利润”？因为利润是结果，现金余额是可以参与转移的中间量。题目说“买入股票”意味着你付出价格，现金减少；卖出则现金增加。把价格直接嵌进状态里，转移方程写起来会顺畅得多。
初始状态怎么定？第 0 天：
- dp[0][0] = -prices[0]，因为第 0 天买入，现金减少 prices[0]。
- dp[0][1] = 0，因为第 0 天什么都不做，现金为 0。
然后从第 1 天开始递推：
- 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])
第一个式子要这样理解：第 i 天持有股票，要么是昨天就持有，今天不动（dp[i - 1][0]）；要么是今天刚买入（-prices[i]）。因为全程只能买卖一次，所以买入前的现金余额恒为 0，直接用 -prices[i] 就行，不需要加上“之前不持有股票时的现金”。这正是121和后面两道题最大的区别——它限定只能买一次，所以“买入”操作只会发生一次。
第二个式子：第 i 天不持有股票，要么昨天就不持有（dp[i - 1][1]）；要么昨天持有、今天卖出，所以是 dp[i - 1][0] + prices[i]，把持有时的现金（负数）加上卖出价格。
最后答案是 dp[n - 1][1]，也就是最后一天不持有股票时的最大现金，因为不卖出哪来的利润。
这个状态设计看起来简单，但它奠定了股票系列DP的统一范式：把每个交易日抽象成“持有”和“不持有”两个状态，再用状态转移来描述买卖动作。后面所有股票题都逃不出这个框架。
代码实现可以压缩成一维滚动数组，因为每一天的状态只依赖前一天：
var maxProfit = function(prices) { let dp = [-prices[0], 0]; for (let i = 1; i < prices.length; i++) { dp[0] = Math.max(dp[0], -prices[i]); dp[1] = Math.max(dp[1], dp[0] + prices[i]); } return dp[1]; };这里有个坑必须提醒：滚动数组更新时，dp[0] 和 dp[1] 有依赖关系。上面的代码里 dp[1] 用的是更新后的 dp[0]，也就是“今天买入再卖出”的情况。但 121 题里同一支股票不能当天买卖，所以用 dp[0] + prices[i] 会不会产生“当天买入当天卖出”的非法情况？不会，因为 dp[0] 更新前的值可能来自今天买入（-prices[i]），但 dp[1] 取的是 Math.max(dp[1], dp[0] + prices[i])，如果今天买入，dp[0] + prices[i] 恰好是 0，不会比原来的 dp[1]（至少是 0 或更大）更优。所以结果不受影响，但理解这个细节很重要，等做到含冷冻期的题目时，这种“同一天买入卖出”的边界就必须专门处理了。
2. 122题的关键跨越：交易次数放开后，买入成本要用累计现金来算
122题把条件改成了“可以多次买卖”，但要求任何时候最多只能持有一股。也就是说，你可以今天卖出，明天再买入，但手里不能同时持有两支以上。
这时候如果继续套121的贪心思路，其实也能解。因为交易次数不限制，只要明天的价格比今天高，今天买入明天卖出就一定能赚，把每段上涨都吃掉，就是最大利润。代码非常短：
var maxProfit = function(prices) { let profit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i - 1]; } } return profit; };但今天练的是动态规划，我们就用DP来做，而且要把状态转移的本质看清楚。
沿用121的状态定义：
- dp[i][0]：第 i 天结束后持有股票的现金余额
- dp[i][1]：第 i 天结束后不持有股票的现金余额
转移方程看起来和121很像：
- 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])
但注意第一个式子变了：121 里是 -prices[i]，因为只能买一次，买入前现金一定是 0；122 里是 dp[i - 1][1] - prices[i]，因为可以多次买卖，你今天买入的时候，手里可能已经攒了之前几轮交易赚到的利润。这个利润就是“不持有股票时手里的现金”，用它减去今天的价格，才是今天买入后的真实现金余额。
这两个式子放在一起看，其实就是一套完整的“状态机”：持有状态和不持有状态互相转换。买入操作让状态从不持有变持有，现金减少；卖出操作让状态从持有变不持有，现金增加。因为交易次数没有上限，状态机可以无限循环跑下去。
看一个例子体会下。假设 prices = [1, 2, 3, 4, 5]，单次买卖最大利润是 4（第 0 天买，第 4 天卖）；多次买卖允许下，仍然最大是 4（每天卖出再买入，相当于持有成本不断重算，但总利润等价）。
模拟一下DP过程：
- 第 0 天：dp[0][0] = -1，dp[0][1] = 0
- 第 1 天：dp[1][0] = Math.max(-1, 0 - 2) = -1；dp[1][1] = Math.max(0, -1 + 3) = 2
- 第 2 天：dp[2][0] = Math.max(-1, 2 - 3) = -1；dp[2][1] = Math.max(2, -1 + 4) = 3
- 第 3 天：dp[3][0] = Math.max(-1, 3 - 4) = -1；dp[3][1] = Math.max(3, -1 + 5) = 4
- 第 4 天：dp[4][0] = Math.max(-1, 4 - 5) = -1；dp[4][1] = Math.max(4, -1 + 6) = 5（等等，第 4 天价格是 5，dp[3][0] + 5 = -1 + 5 = 4）
我重新算准确一点，价格数组 [1, 2, 3, 4, 5]：
- 第 0 天：持有 = -1，不持有 = 0
- 第 1 天（价格 2）：持有 = Math.max(-1, 0 - 2) = -1；不持有 = Math.max(0, -1 + 2) = 1
- 第 2 天（价格 3）：持有 = Math.max(-1, 1 - 3) = -1；不持有 = Math.max(1, -1 + 3) = 2
- 第 3 天（价格 4）：持有 = Math.max(-1, 2 - 4) = -1；不持有 = Math.max(2, -1 + 4) = 3
- 第 4 天（价格 5）：持有 = Math.max(-1, 3 - 5) = -1；不持有 = Math.max(3, -1 + 5) = 4
最终答案 4，符合预期。可以观察到持有状态一直保持 -1，说明最优策略是第 0 天买入后再也没换过手；而“不持有”从 1 涨到 4，是因为 DP 把“持有不动”的利润在“不持有”状态里滚起来了。这个滚动过程，就是122题和121题的本质区别。
代码实现上，一维滚动数组依然适用：
var maxProfit = function(prices) { let dp = [-prices[0], 0]; for (let i = 1; i < prices.length; i++) { let temp = dp[0]; dp[0] = Math.max(dp[0], dp[1] - prices[i]); dp[1] = Math.max(dp[1], temp + prices[i]); } return dp[1]; };这里为什么用 temp 暂存旧的 dp[0]？因为计算 dp[1] 时，需要的是“今天的操作之前”的持有状态，也就是 dp[0] 更新前的值。122题里，dp[1] 用新的 dp[0] 相当于“今天买入再卖出”，在今天价格比昨天高时，这可能导致多算一段无意义的利润。虽然在这个场景下不会影响最终结果（多算的那段会在后续转移中被修正），但养成用中间变量保存旧值的习惯，到了含冷冻期、含手续费这类变体题时能少踩很多坑。
3. 123题的硬骨头：两笔交易的状态空间翻倍，边界初始化必须抠细
123题把难度推到了新的高度：最多可以完成两笔交易，也就是说你可能只交易一次，也可能交易两次，但不能超过两次。注意，这里两次交易不能重叠——你必须在第二次买入之前把第一次持有的股票卖掉。
拿到这道题，第一反应可能是：把数组劈成两段，前一段做一次121，后一段做一次121，遍历分割点取最大值。这个思路叫“分段DP”，复杂度 O(n²)，虽然能过小数据，但不够优雅，而且分段点遍历时“前一段最大值”可以预处理成前缀数组，“后一段最大值”可以预处理成后缀数组，这样确实可以优化到 O(n)。不过今天既然要学状态机，我们直接用更统一的状态设计。
核心突破点在于：交易次数从 1 次变 2 次，状态不能再只是“持有/不持有”两个状态了，因为“不持有”可能是第一次卖出后的空仓，也可能是第二次卖出后的空仓。两者后续能做的操作完全不同——前者还能再买入一次，后者已经不能买了。所以必须把“交易进行到第几笔”这个信息编进状态里。
于是得到四个状态：
- dp[i][0]：第一次买入后（持有第一支股票）的最大现金
- dp[i][1]：第一次卖出后（完成第一笔交易且当前空仓）的最大现金
- dp[i][2]：第二次买入后（持有第二支股票）的最大现金
- dp[i][3]：第二次卖出后（完成第二笔交易且当前空仓）的最大现金
严格来说，状态顺序可以按时间逻辑排：第一次买入、第一次卖出、第二次买入、第二次卖出。这个顺序也是转移的方向。
转移方程怎么写？每个状态依然是两种可能：今天保持昨天的状态，或者今天执行了“进入该状态”的动作。
- dp[i][0] = Math.max(dp[i - 1][0], -prices[i])。第一次买入前手里现金一定是 0，所以买入成本直接是 -prices[i]。
- 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 - 1][1]）减去今天的价格。这是整道题的核心——第二次买入的成本，是建立在第一笔交易利润之上的。
- dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i])。第二次卖出，利润结清。
初始值怎么定？这是最容易翻车的地方。第 0 天：
- dp[0][0] = -prices[0]，买入第一支，现金减少。
- dp[1] 呢？第 0 天不可能已经完成第一笔卖出，所以是“无意义状态”。但如果直接设 0，会让第 1 天计算 dp[i][2] 时出现“凭空多出一次买入机会”的问题。更安全的方式是设成一个极小值（比如 -Infinity），表示这个状态不可达。
- dp[0][2] = -prices[0]。这里很多人会惊讶：第 0 天怎么可能完成第二次买入？但仔细想，题目允许“当天买入当天卖出再买入”吗？不允许，因为必须“卖出后才能再买入”，而且一天只有一个价格，当天买入当天卖出利润为 0，再买入相当于还是持有。但 DP 的初始值如果设成 -prices[0]，表示“第 0 天进行了一次利润为 0 的第一笔买卖，然后立刻第二次买入”，利润不变，但交易次数先用了一次。这样设置后，后续转移中 dp[2] 可以在任意一天被更新，相当于允许“只做一笔交易”的情况存在——因为第一笔交易的利润可以是 0。
- dp[0][3] = -Infinity 或 0？想一想：第 0 天不可能完成两笔完整交易（需要至少两天），所以设成 -Infinity 更严谨。但如果你设成 0，也不会影响最终答案，因为 dp[3] 至少不会低于 0（不交易也是 0）。为了逻辑一致性，建议把不可能的状态都初始化为 -Infinity，只把 dp[0][0] 和 dp[0][2] 初始化为 -prices[0]，dp[0][1] 和 dp[0][3] 初始化为 0。
等等，dp[0][3] 设成 0 不是不对吗？我再捋一下：答案最终取的是 dp[n - 1][3] 和 dp[n - 1][1] 的最大值，因为最优策略可能只交易了一笔，也可能两笔。如果 dp[0][3] = 0，表示“第 0 天完成了两笔零利润的交易”，这在后续转移中会让 dp[3] 有了一条“纯 0 基线”，某些情况下会掩盖真实利润。但实际上，因为 dp[3] = Math.max(dp[3], dp[2] + prices[i])，而 dp[2] 初始是 -prices[0]，第一天 dp[2] + prices[1] 可能为负，所以 dp[3] 会保持 0；到后面 dp[2] + prices[i] 大于 0 时，更新就发生在真实交易之后。所以设 0 只是给“不交易”留了一条路，不影响正确性。但为了概念纯净，代码里我建议：
var maxProfit = function(prices) { let dp = [ -prices[0], 0, -prices[0], 0 ]; for (let i = 1; i < prices.length; i++) { const next = [...dp]; next[0] = Math.max(dp[0], -prices[i]); next[1] = Math.max(dp[1], dp[0] + prices[i]); next[2] = Math.max(dp[2], dp[1] - prices[i]); next[3] = Math.max(dp[3], dp[2] + prices[i]); dp = next; } return Math.max(dp[1], dp[3]); };注意这里我用了 next 数组，把四个状态都基于“昨天的旧值”来更新。如果同一天内从左到右顺序更新，比如先更新 dp[0] 再更新 dp[1]，那 dp[1] 可能用到今天刚更新的 dp[0]，这意味着“今天买入、今天卖出”，虽然没有实际利润影响，但为了严谨，建议复制一份旧状态。
为什么最终答案要取 dp[1] 和 dp[3] 的最大值？因为最优解法可能只做了一笔交易，这时候 dp[3] 可能仍然停留在“不交易”的 0 基线，或者被一个负的中间状态干扰，取最大值更稳妥。
看一个完整例子。prices = [3, 3, 5, 0, 0, 3, 1, 4]，这是 LeetCode 官方示例，预期答案是 6（第 3 天买，第 5 天卖，赚 3；第 6 天买，第 7 天卖，赚 3，合计 6）。
我手动推一遍核心节点：
- 初始：dp = [-3, 0, -3, 0]
- 第 1 天（价格 3）：
- next[0] = Math.max(-3, -3) = -3
- next[1] = Math.max(0, -3 + 3) = 0
- next[2] = Math.max(-3, 0 - 3) = -3
- next[3] = Math.max(0, -3 + 3) = 0
- 第 2 天（价格 5）：
- next[0] = Math.max(-3, -5) = -3
- next[1] = Math.max(0, -3 + 5) = 2
- next[2] = Math.max(-3, 0 - 5) = -3
- next[3] = Math.max(0, -3 + 5) = 2
- 第 3 天（价格 0）：
- next[0] = Math.max(-3, 0) = 0（这是“第 3 天买入”的成本 0）
- next[1] = Math.max(2, -3 + 0) = 2
- next[2] = Math.max(-3, 2 - 0) = 2（注意！这里表示：第 2 天卖出了第一笔赚 2，然后第 3 天以 0 元买入第二次，手里现金 2）
- next[3] = Math.max(2, -3 + 0) = 2
- 第 4 天（价格 0）：
- next[0] = Math.max(0, 0) = 0
- next[1] = Math.max(2, 0 + 0) = 2
- next[2] = Math.max(2, 2 - 0) = 2
- next[3] = Math.max(2, 2 + 0) = 2
- 第 5 天（价格 3）：
- next[0] = Math.max(0, -3) = 0
- next[1] = Math.max(2, 0 + 3) = 3
- next[2] = Math.max(2, 2 - 3) = 2
- next[3] = Math.max(2, 2 + 3) = 5
- 第 6 天（价格 1）：
- next[0] = Math.max(0, -1) = 0
- next[1] = Math.max(3, 0 + 1) = 3
- next[2] = Math.max(2, 3 - 1) = 2（注意这里 3 是 dp[1] 的旧值，不是 next[1]）
- next[3] = Math.max(5, 2 + 1) = 5
- 第 7 天（价格 4）：
- next[0] = Math.max(0, -4) = 0
- next[1] = Math.max(3, 0 + 4) = 4
- next[2] = Math.max(2, 3 - 4) = 2
- next[3] = Math.max(5, 2 + 4) = 6
最终 dp[3] = 6，结果正确。注意上面第 6 天的计算里，next[2] 用的是 dp[1]（旧的 3），而不是当天刚算出的 next[1]。这就是为什么我强调要基于“昨天的状态”来更新——如果顺序更新，next[2] 会变成 next[1] - 1 = 2，碰巧结果一样，但概念上已经错了。当状态数变多、依赖变复杂时，这种“同一天内状态串联”的bug会让人排查到怀疑人生。
4. 从1笔到2笔到k笔：状态设计的递推规律与刷题方法论
三道题做下来，能明显看到一条递进的主线。我用一张表总结：
| 题目 | 持有状态数 | 核心状态转移变化 | 关键突破点 |
|---|---|---|---|
| 121 | 2个（持有/不持有） | 买入用 -prices[i]，卖出用 dp[0] + prices[i] | 只能买一次，买入成本固定为 0 |
| 122 | 2个（持有/不持有） | 买入改用 dp[1] - prices[i]，卖出不变 | 可多次交易，买入成本要用累计现金 |
| 123 | 4个（两笔交易各自的持有/卖出） | 第二次买入用 dp[1] - prices[i]，第二次卖出用 dp[2] + prices[i] | 交易次数受限，需要记录“第几笔” |
如果把 123 推广到“最多 k 笔交易”的188题，思路就非常清晰了：把状态数组扩成 2k 维，dp[i][2j] 表示第 j+1 次持有，dp[i][2j+1] 表示第 j+1 次卖出后的空仓。转移方程是：
- dp[i][2j] = Math.max(dp[i-1][2j], dp[i-1][2*j-1] - prices[i])
- dp[i][2j+1] = Math.max(dp[i-1][2j+1], dp[i-1][2*j] + prices[i])
其中 j 从 1 开始，第一次买入的特殊性在于 dp[i-1][-1] 不存在，所以直接是 -prices[i]。
这就是为什么我反复强调要在121题就把“持有/不持有”两个状态吃透——因为股票系列的所有变体题（含冷冻期、含手续费、k笔交易）都是在这个状态机上做加减法。
再分享几个实战中的经验。
第一，初始化的 -Infinity 不是可选项，是必须项。我一开始做 123 题时，把 dp[0][3] 设成 0，后面调试时发现答案在某些极端输入下会偏大。后来仔细推敲才发现，dp[3] 从 0 开始会让“什么都没做”的情况在边界上干扰真实利润的累计。虽然很多题解里设 0 也能过，但那是因为数据没有触发边界问题。做技术还是严谨点好，不可能的初始状态全部设 -Infinity，只把真正可达的状态给有效值。
第二，滚动数组更新必须保留“昨日镜像”。123 题的四个状态如果 left-to-right 顺序更新，虽然大多数测试用例碰巧能过，但这个 bug 是潜伏的。等做到 188 题 k 笔交易，状态维度一多，顺序更新几乎必然出错。我建议要么用一个 next 数组存新值，要么从后往前更新（后更新的状态依赖先更新的旧值）。更通用的习惯是：只要状态转移存在交叉依赖，就复制一份旧的再算。
第三，不要被题目绕进“第几天买、第几天卖”的具体推演里。做动态规划题，最大的思维陷阱是总想还原每一步的真实操作。但 DP 并不保证每个状态都有确切的交易路径，它只是维护了一个“可能性集合”的最优值。比如 123 题的 dp[2] 初始化为 -prices[0]，现实中并不存在“第 0 天第二次买入”的操作，但这个初始化让后续转移能够覆盖“只交易一次”的最优解。想清楚这一点，你就不会被状态的“语义”卡住，而是更关注转移方程是否覆盖了所有合法路径。
第四，写题之前先想清楚“状态之间能否互相到达”。我在带朋友刷题时发现，很多人把状态定义背下来、转移方程套上去，但一遇到题目变体就懵。根本原因是没有理解状态图。其实你可以把 121、122、123 的状态转移画成一张有向图：持有和空仓是两个节点，买入和卖出是两条边；交易次数限制只是给这个图加了一层“剩余次数”的维度和“某些边只能走一次”的约束。理解到这一层，后面做 309（含冷冻期）、714（含手续费）就只是改边的权重和走向的问题。
今天这三道题还有一个实操层面的收获：遇到序列类 DP 题，先列状态变量，再写转移方程，最后补初始化，这个顺序不要乱。特别是初始化，它是初学者最容易丢分的地方——状态定义的边界条件没想清楚就动手写代码，debug 的时间往往比写代码的时间还长。
最后说一句：刷算法题不要追求“背模板”，而是要把每道题背后的状态设计逻辑盘明白。买卖股票这个系列是最好的练习素材，因为它从简到繁覆盖了 DP 状态设计的所有关键技巧——单状态、双状态、多维状态、状态压缩。三道题练完，动态规划里最磨人的“状态怎么想出来”这个问题，你会比之前通透很多。
