状态机 DP

六道题，一个模型

力扣的股票买卖是一个系列：121（只能交易一次）、122（不限次数）、 123（最多两次）、188（最多 k 次）、309（有冷冻期）、714（有手续费）。

⚠️ 如果一道一道背，就是六套代码。它们其实是同一道题。

⭐ 转换的关键一步：别想「什么时候买、什么时候卖」，想「每一天我处于什么状态」。

        买入
   ┌──────────────┐
   ↓              │
[持有]          [不持有]
   │              ↑
   └──────────────┘
        卖出

每天只有两种身份：手上有股票、手上没有股票。 买入和卖出是这两个状态之间的边。求最大利润 = 在这张图上走 n 天， 最后停在「不持有」，路径上的收益最大。

📌 这就是「状态机 DP」这个名字的来源：状态是图上的点，转移是边。

基础框架

// dp[i][0] = 第 i 天结束时「不持有」的最大利润
// dp[i][1] = 第 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]);   // 不动 / 买入

⭐ 这两行读出来就是人话： 「今天不持有，要么昨天就不持有、今天啥也没干，要么昨天持有、今天卖了。」

因为每一行只依赖前一天，可以直接压成两个变量：

function maxProfit(prices) {              // 力扣 122：不限交易次数
  let hold = -Infinity, free = 0;
  for (const p of prices) {
    const prev = free;                        // ⭐ 先把昨天的 free 存下来
    free = Math.max(free, hold + p);
    hold = Math.max(hold, prev - p);          // ⚠️ 用的必须是昨天的 free
  }
  return free;
}

⚠️ 一条被到处复制、但在这道题上不成立的告诫

几乎每篇讲状态压缩的文章都会说：压成变量后要小心「用的是今天的还是昨天的」。 按这个说法，下面这版应该是错的：

free = Math.max(free, hold + p);
hold = Math.max(hold, free - p);   // 用的是「今天的」 free

但它在 122 上是对的。 5000 组随机数据实测， 和正确写法零差异。

⭐ 原因值得想清楚：用今天的 free 买入，含义是「今天卖掉、又在今天买回来」。 同价买卖的净收益是 0 —— 这条转移永远不会让答案变大，也不会让它变小。 它是一条无害的多余边。

🚨 别把这条经验推广：同样的方向问题在 0-1 背包上是真 bug。 2000 组随机数据里（物品 18 件、容量 112、重量 16、价值 110）， 正序和倒序有 70% 不一样：

W=6  重量 [1,2,6,1]  价值 [5,8,2,4]
   倒序（正确）  17
   正序          30   ← 同一件物品被拿了多次

📌 差别在于：背包里正序意味着「同一件物品拿两次」，那是实实在在多出来的收益； 股票里正序意味着「同日买卖」，那是零收益操作。 ⭐ 判断方向要不要紧，得看多出来的那条转移会不会改变最优值， 不能靠背「一维压缩要倒序」。

⚠️ 下面 309 冷冻期那一节里，同样的顺序问题就真的会错 —— 因为那时「昨天」和「前天」是题目语义的一部分，不再是实现细节。 （错的比例完全取决于测试数据的形状，从 4% 到 100%，那一节有一张表。）

🚨 hold 的初值为什么必须是 -Infinity

这是这个系列最容易踩、也最值得理解的一个点。

hold = 0 的意思是「第 0 天之前我就已经持有股票，而且没花钱」—— 白捡一支股票。实测两种初值（前四行是 122 不限次数，最后一行是 k=2）：

输入                       正确   hold 初值写 0   差
[5]                          0         5         5
[2,1]                        0         2         2
[7,6,4,3,1]（单调下降）       0         7         7
[7,1,5,3,6,4]                7        14         7
[3,3,5,0,0,3,1,4] (k=2)      6         9         3

⚠️ [5] 那一行最能说明问题：只有一天、什么都做不了， 正确答案必须是 0，而 hold = 0 的版本凭空赚了 5 块 —— 它把「免费得到的股票」在第一天卖掉了。

🚨 顺带提防一处容易记混的地方：[7,1,5,3,6,4] 是 121（只能交易一次） 的经典样例，那道题的答案是 5（买 1 卖 6）。但上表用的是 122（不限次数） 的实现，答案是 7（1→5 赚 4、3→6 赚 3）。 ⚠️ 这一行以前就写着 121 的那个 5 —— 同一个数组在六道题里有六个答案， 抄样例的时候连答案一起抄，就会串台。

⭐ 错误量有闭式解：恰好多赚一个 prices[0]

看上表最后一列：差值分别是 5、2、7、7 —— 正是每个输入的 prices[0]。 （k=2 那行差 3，那是 k 有限时被额度截断的情形。）

不限次数时这是可以推出来的，不必靠统计： 白捡的那支股票最优处置是第 0 天立刻卖掉（得 prices[0]）， 因为卖掉后当天就能重新买入，后续的交易空间分毫不受影响。

hold 初值写 0 的答案 ≡ 正确答案 + prices[0]

穷举 n=18、值域 03 的全部 87380 组，零例外。

🚨 于是「它在每一个测试用例上都出错」这个说法不成立（这里以前就是这么写的）： prices[0] === 0 时两者完全相同，空数组也相同。 2 万组随机数据里有 2869 组答案一致 —— 其中空数组 1968 组、 首日价格为 0 的 797 组、全为 0 的 104 组。

⭐ -Infinity 表达的是「这个状态不可达」。 📌 这是所有 DP 的通用约定：base case 里不合法的状态用 ±Infinity， 不要用 0 —— 0 是一个合法的值，会被 max 当成真实方案选中。

📌 和树形 DP 里那两个相比， 这个错响得大声得多（差值等于首日价格，只要首日价格不为 0 就露）， 但它并不是「必然露」——判据是 prices[0] !== 0，不是「所有用例」。

加维度：交易次数 k

121（k=1）、123（k=2）、188（k 任意）的区别只是多一个维度：

// dp[k][0] / dp[k][1]：还剩 k 次交易额度时，不持有 / 持有 的最大利润
function maxProfitK(K, prices) {
  const n = prices.length;
  if (!n || K === 0) return 0;

  // ⭐ k >= n/2 时额度用不完，等价于不限次数（122）
  if (K >= n / 2) {
    let sum = 0;
    for (let i = 1; i < n; i++) sum += Math.max(0, prices[i] - prices[i - 1]);
    return sum;
  }

  const dp = Array.from({ length: K + 1 }, () => [0, -Infinity]);
  for (let i = 0; i < n; i++)
    for (let k = K; k >= 1; k--) {                 // 🚨 k 倒序，见下
      dp[k][0] = Math.max(dp[k][0], dp[k][1] + prices[i]);
      dp[k][1] = Math.max(dp[k][1], dp[k - 1][0] - prices[i]);
    }
  return dp[K][0];
}

三个要点：

① 额度在哪一步消耗。 上面写的是买入时消耗（dp[k-1][0]）。 写成卖出时消耗也行，但必须全程一致 —— 混着写会算出多一次或少一次交易。

② k 的方向。 上面写的是倒序。很多题解会说「必须倒序， 否则 dp[k-1][0] 已经被今天更新过，就成了同一天用两次额度」。

⚠️ 这个理由对，但结论不成立。 实测：3000 组随机数据对着暴力解校验， 正序、倒序都完全正确；再拿 n ≤ 45、K ≤ 6 的 2000 组比对两种顺序， 零差异。

⭐ 还是那个原因：同一天用两次额度 = 同价买卖 = 零收益，最优值不受影响。 📌 倒序仍然值得写 —— 它让代码的含义和你脑子里的推导一致， 而不是靠「恰好无害」蒙混过去。但别把它当成正确性的必要条件。

③ K >= n/2 的短路。 一次完整交易至少占两天， 所以 n 天里最多做 n/2 次。不加这个判断，188 传进来 k = 10⁹ 会直接爆内存。 ⚠️ 这不是优化，是必须的。

122 的贪心为什么等价

不限次数时，常见写法是「把所有上涨段的差值加起来」：

let sum = 0;
for (let i = 1; i < n; i++) sum += Math.max(0, prices[i] - prices[i - 1]);

⭐ 它和状态机 DP 完全等价 —— 2000 组随机数据实测结果一模一样。

原因：[1, 5] 涨了 4，拆成 [1,3] 的 2 加 [3,5] 的 2 也是 4。 不限次数意味着可以把一次长交易拆成任意多次短交易， 所以「吃掉每一段上涨」和「找最优买卖点」是同一件事。

🚨 但这个贪心只在 k = ∞ 时成立。k 有限时必须用 DP —— 你得挑出「哪几段上涨最值钱」，那是选择问题，贪心不管用。

加状态：冷冻期与手续费

309 冷冻期（卖出后一天不能买）：卖出之后要经过一个「冷冻」状态才能回到可买。 不用真的加第三个点，只要买入时看的是前天的 free：

function maxProfitCooldown(prices) {
  let hold = -Infinity, free = 0, prevFree = 0;   // prevFree = 前天的 free
  for (const p of prices) {
    const t = free;
    free = Math.max(free, hold + p);
    hold = Math.max(hold, prevFree - p);          // 🚨 前天，不是昨天
    prevFree = t;
  }
  return free;
}

⚠️ 实测 [1,2,3,0,2]：

正确答案                        3
完全忘记冷冻期（当成 122）        4
prevFree 误写成 free            4

📌 两个不同的错症状完全一样 —— 都是 4。 所以「答案偏大 1」这个现象没法区分是哪个原因，得回去读代码。

🚨 ⭐ 注意对比上面 122 那一节：那里 prev 和 free 混用完全无害 （穷举 n≤6、值域 0~3 的全部 5461 组也零差异），这里同一个混用真的会错。

⚠️ 但「错多少比例」这个问题没有一个数字能回答 —— 它完全由数据口径决定。 同一个错法，5000 组随机数据实测：

价格序列长度	值域 0~2	值域 0~9	值域 0~99
0~5	4.4%	7.7%	9.3%
0~10	19.9%	31.8%	36.7%
0~30	58.5%	71.7%	74.9%
30~60	97.9%	99.9%	100%

📌 序列越长、值域越大，越容易撞上「当天卖当天买」能占到便宜的形状。 （这一节以前写的是「29% 出错」，那大约对应「长度 010、值域 09」那一格 —— 而没写口径的百分比，读者换个生成器就得到 4% 或 100%。） ⭐ 所以这个数字该读成「会错」，不该读成「错得多频繁」。

差别在于加了冷冻期之后，「隔一天」不再是实现细节，而是题目规则本身 —— 用今天的 free 买入，等于允许了当天卖出当天买回，正是冷冻期禁止的事。

714 手续费：更简单，卖出时扣掉就行。

free = Math.max(free, hold + p - fee);   // ⭐ 只改这一处

⭐ 手续费必须只扣一次（要么买时扣要么卖时扣，别两边都扣）。

六道题的对照

题	状态数	相对基础框架的改动
121 k=1	2	买入时从 0 转移（不能累加之前的利润）
122 k=∞	2	就是基础框架；也可以用贪心
123 k=2	2×3	加一维 k（方向不影响正确性，见上）
188 k任意	2×(k+1)	同上 + K >= n/2 短路
309 冷冻期	2（+1 延迟）	买入看前天的 free
714 手续费	2	卖出时 - fee

⭐ 六道题里，只有 123/188 真的多了一个维度，其余四道都是两个状态、 改一两个符号的事。

不只是股票

状态机 DP 的适用范围比股票宽得多。判据是：

每个位置有几种「身份」，身份之间的转移有规则。

• 打家劫舍（198）：状态 = 这间偷 / 不偷，规则 = 相邻不能都偷
• 粉刷房子（256）：状态 = 刷成红/蓝/绿，规则 = 相邻不能同色
• 交错字符串 / 正则匹配：状态 = 匹配到哪、是否处于通配

function rob(nums) {                       // 198：和股票是同一个骨架
  let no = 0, yes = 0;
  for (const x of nums) {
    const prevNo = no;
    no = Math.max(no, yes);                // 不偷这间：上一间随意
    yes = prevNo + x;                      // 🚨 偷这间：上一间必须没偷
  }
  return Math.max(no, yes);
}

📌 和上面的股票代码放在一起看 —— 两个变量、每轮各自从对方更新、 注意别用到今天的值。骨架一模一样。

⭐ 而「别用到今天的值」这句告诫，在这三处的分量完全不同 —— 把它量出来，就不用靠背了（把 prevNo / prev 改成当天的值，2 万组随机数据）：

哪一处	用今天的值会怎样
122 股票（k=∞）	零差异（连穷举 5461 组也一样）—— 多出来的是「同价买卖」，收益 0
198 打家劫舍	85.9% 出错 —— 多出来的是「相邻两间都偷」，那是实实在在的收益
309 冷冻期	会错，比例见上面那张表 —— 多出来的正是题目禁止的操作

🚨 判据始终是同一条：看那条多出来的转移会不会改变最优值。 「一维压缩要倒序」「别用今天的值」都是经验规则，不是定理 —— 它们在 122 上恰好无害，在打家劫舍上是六成以上的错。

⭐ 顺带：树形 DP 里的打家劫舍 III 就是把这个状态机搬到树上，[no, yes] 从两个变量变成递归的返回值。 状态机的形状没变，只是遍历的结构从数组变成了树。

状态形状总表

子问题视角这一章的 DP 部分到此为止。 把状态的形状排一排，整章就是一句话：先想清楚状态是什么，方程是自然的结果。

状态定义在	类型
前 i 个 / 以 i 结尾	子序列问题
前 i 个 + 剩余容量	背包问题
区间 [i..j]	区间 DP
树的一个节点	树形 DP
位置 + 当前身份	状态机 DP

下一步

上面每一类的最后一步都是同一件事：降维。 两个变量代替一整行、一行代替一整张表 —— 这就是状态压缩， 以及什么时候不该压。

练习

勾选记录做过哪些，0 / 7 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

• 121. 买卖股票的最佳时机简单k=1。买入时从 0 转移，不能累加之前的利润
• 122. 买卖股票的最佳时机 II中等k=∞，就是基础框架；也能用「吃掉每段上涨」的贪心，两者等价
• 714. 买卖股票的最佳时机含手续费中等只改一处：卖出时减 fee。注意别买卖两头都扣
• 309. 买卖股票的最佳时机含冷冻期中等⭐ 本系列唯一一道「更新顺序真会出错」的题——买入要看前天的 free
• 123. 买卖股票的最佳时机 III困难k=2，加一维；先用二维数组写清楚，再考虑压
• 188. 买卖股票的最佳时机 IV困难k 任意。⚠️ 必须加 K >= n/2 的短路，否则 k=10^9 直接爆内存
• 740. 删除并获得点数中等⭐ 伪装的打家劫舍：按值域排开之后，「选了 x 就不能选 x±1」= 相邻不能都选

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。