15.2　状态定义与转移方程

学习目标：学完本节，你能

用一句话说清什么是"状态"，以及它必须满足的那条判据；
用四个自检问题检查自己的状态定义是否成立；
用"枚举最后一步"这个手法推导转移方程；
亲手体验一次"状态定义差一个词，答案就错了"（本节有实测反例）。

先修：15.1（记忆化、重叠子问题）、14.1（贪心与 DP 的分界）。 固定术语：状态转移方程、记忆化、动态规划。 环境与版本：.NET 8 / C# 12。 预计阅读：38 分钟。

一、直觉：状态是"决定未来的那一小撮信息"

15.1 节用一个修好的斐波那契演示了记忆化，但它有一个"作弊"的地方：

斐波那契的状态就是那个整数 $n$ —— 参数是什么，状态就是什么，根本不用动脑子。

面对一个新问题，第一个要回答的问题永远是：

我该拿什么当"状态"？

先看一个场景。小陈在写一个"爬楼梯"的题：每次可以走 1 级或 2 级，问走到第 $n$ 级有几种走法。

他站在第 5 级台阶上，想往后走 ——

他需要知道什么？

"我还剩几级要走" —— 也就是 $n$。

那"我是怎么走到第 5 级的"（1+2+2 还是 2+2+1）呢？

不需要知道。 因为不管怎么来的，剩下的走法数都一样。

这句话就是"状态"的定义：

状态（State）：求解过程中，"决定未来"的那一小撮信息 ——

把它写下来，就足以推断后面的一切；不写下来，后面就算不出来。

形式化一点的判据（本节最重要的一条）：

如果两个局面的【状态相同】，那么它们【后续的最优解也完全相同】。

—— 这条成立，状态就定义对了；不成立，状态就不够。

用这条判据检验爬楼梯：

局面 A	局面 B	状态相同吗	未来相同吗
还剩 3 级，从 1+2 来的	还剩 3 级，从 2+1 来的	相同（都是"剩 3 级"）	相同（都是 3 种走法）✓

"怎么来的"被正确地忽略掉了 —— 这正是状态该做的事。

二、四个自检问题

定完状态之后，用这四个问题过一遍：

#	问题	答错的症状
1	它够吗？两个状态相同的局面，往后走的结果会不会不同？	答案算错（漏了信息）
2	它多吗？有没有两个不同的状态，其实描述的是同一个局面？	白算（状态数虚高）
3	算得动吗？状态总数 $=$ 各维度取值数的乘积，能不能承受？	内存/时间爆炸
4	转移只看它吗？从状态 A 推出状态 B 时，需不需要知道"我是怎么走到 A 的"？	答案算错（同 15.1 的缓存合法性）

第 1 问和第 4 问其实是一回事的两面：

第 1 问问的是"信息够不够"，第 4 问问的是"信息是不是【只】来自状态本身"。 两者都指向同一条要求：状态必须是【未来的充分摘要】。

第 3 问最容易被忽略，也最容易致命：

状态总数是【各维度取值数的乘积】。

一个二维状态 $1000 \times 1000$ 是 100 万个格子 —— 能接受；加一个维度变成 $1000 \times 1000 \times 1000$ 就是 10 亿 —— 直接爆掉。

所以"多一个维度"这件事，代价是【乘法级】的 —— 这正是 15.4 节"空间优化"要处理的问题。

三、转移方程：从"枚举最后一步"来推

状态定好了，下一步是写出"怎么从更小的状态推出来"。

通用的推导手法只有一句话：

枚举【最后一步】的所有可能。

看它在三个问题上怎么用：

问题	最后一步是什么	转移方程
爬楼梯	最后一步是走 1 级，还是走 2 级？	$f(n) = f(n-1) + f(n-2)$
打家劫舍	最后一家是偷，还是不偷？	$f(i) = \max(f(i-1),\ f(i-2) + a_i)$
最长递增子序列	最后一步是接在哪个 $j$ 后面？	$dp[i] = \max_{j<i,\ a_j < a_i} dp[j] + 1$

注意这三个方程的形状完全一样：

左边是"当前状态"，右边是"若干个更小的状态" + "这一步的收益"。

区别只在于"更小的状态"是谁 —— 而这完全由第 1 步的状态定义决定。

四、例题一：爬楼梯（热身）

问题：楼梯有 $n$ 级，每次可以走 1 级或 2 级，有多少种走法？

第 1 步：定义状态。

$f(n)$ = 走到第 $n$ 级的方法数

四问自检：

够吗？ 只剩几级决定一切，"怎么上来的"不重要 ✓

多吗？ 每个 $n$ 对应一个真实局面 ✓

算得动吗？ $n+1$ 个状态，一维数组就够 ✓

转移只看它吗？ 是 ✓

第 2 步：枚举最后一步。

走到第 $n$ 级的最后一步，只有两种可能：

从第 $n-1$ 级走 1 级上来 → 前面有 $f(n-1)$ 种走法

从第 $n-2$ 级走 2 级上来 → 前面有 $f(n-2)$ 种走法

所以：$f(n) = f(n-1) + f(n-2)$

第 3 步：边界条件。

$f(0) = 1$（站在地面，一种走法：什么都不做） $f(1) = 1$（只能走 1 级）

这个方程和斐波那契一模一样 —— 但推导过程完全不同：斐波那契是"定义给的"，爬楼梯是"枚举最后一步推出来的"。

这正是 DP 的通用套路：先定状态，再枚举最后一步，最后补边界。

五、例题二：LIS —— 状态定义差一个词

问题：在一个数组里找出最长的严格递增子序列（不要求连续）。

先看一个非常自然、但错误的状态定义：

  错误的状态定义：f[i] = 【前 i 个元素】的最长递增子序列长度

这个定义看起来很合理 —— "前 i 个里最长有多长"，正是我们想求的东西。

实测（反例数组 [4, 5, 1, 2, 3]）：

  错误的状态定义：f[i] = 【前 i 个元素】的最长递增子序列长度
    f = [1, 2, 2, 3, 4]  ->  答案 4

  正确的状态定义：dp[i] = 【以 a[i] 结尾】的最长递增子序列长度
    dp = [1, 2, 1, 2, 3]  ->  答案 3

  暴力枚举所有子序列：3

错误版说是 4，正确答案是 3。

错在哪？

[4, 5, 1, 2, 3] 的真实 LIS 是 1, 2, 3（长度 3） —— 4, 5 虽然自己递增，但它们后面接不上 1。

而错误版在算 f[2] 时是这么想的：

  a[2] = 1，比 a[1] = 5 小 —— 涨不上去，所以 f[2] = f[1] = 2

它把 f[1] = 2 保留了下来 —— 意思是"前 3 个元素里最长有 2"。

这句话本身没错（4,5 确实是长度 2 的递增子序列），但它丢掉了一个关键信息：

那条长度 2 的子序列，结尾是 5。

后面无论来什么比 5 小的数，都接不上它 —— 而 f[2] 这个数【看不出这一点】。

所以错误版一路把 f 撑到了 4（4,5 那条链被反复"继承"下去），而实际上它早就断了。

第 1 问（"它够吗？"）在这里失败了：

"前 i 个的 LIS 长度"丢失了"结尾是什么"这条信息 —— 而"能不能接上后面的数"，恰恰只由结尾决定。

正确的定义

  dp[i] = 【以 a[i] 结尾】的最长递增子序列长度

转移方程（枚举最后一步：接在哪个 j 后面）：

$$dp[i] = \max_{\substack{j < i \ a_j < a_i}} dp[j] + 1$$

边界：每个 $dp[i]$ 至少是 1（它自己单独成一个子序列）。

答案：$\max_i dp[i]$ —— 注意不是 dp[n-1]。

这个"答案是 max 而不是最后一个"的细节，也是状态定义的直接后果：

既然 dp[i] 的含义是"以 $a_i$ 结尾"，那答案自然要在所有可能的结尾里挑最大的。

错误版错得有多频繁？

  3000 组随机数组（长度 5~12，元素 1~9），与暴力枚举对比：

    错误的状态定义： 1123 / 3000 组正确（37.4%）
    正确的状态定义： 3000 / 3000 组正确（100.0%）

37.4% —— 和 14.1 节那个"贪心找零"是同一类现象：

它不是"总是错"，而是"有时错" —— 随机试几个例子很可能蒙对，然后你就把它提交了。

而且它错的时候不会报错，只会给一个偏大的数 —— 这种错误最难查。

六、例题三：打家劫舍 —— 状态不是越多越好

问题：一排房子各有金额，不能偷相邻的两家，求最多能偷多少。

小陈的第一反应是：

"我得记住上一家偷没偷啊" —— 因为如果上一家偷了，这一家就不能偷了。

听起来很有道理。于是有两种状态定义：

	状态定义	维度
简洁版	$f(i)$ = 前 $i$ 家的最大金额	一维
多维版	$f(i, \text{第 } i \text{ 家偷没偷})$	二维（状态数翻倍）

实测（例子 [2, 7, 9, 3, 1]）：

    简洁版（一维）：rob(i) = max(rob(i-1), rob(i-2) + a[i])  ->  12
    多维版（二维）：rob(i, 偷没偷)                          ->  12
    暴力枚举所有「不相邻」的选法                            ->  12

两种定义都对，结果一样。 3000 组随机数据对拍：不一致 0 组。

为什么一维就够了？

因为"第 $i$ 家偷没偷"这条信息，已经被 $f(i-1)$ 和 $f(i-2)$ 的组合隐含了：

  f(i-1)            对应「不偷第 i 家」—— 那前面爱怎么偷怎么偷，取最优就行
  f(i-2) + a[i]     对应「偷第 i 家」  —— 那第 i-1 家必然没偷，所以看 f(i-2)

两条分支刚好把两种可能【都覆盖了】，所以不需要额外记一个标志位。

这就是"状态多不多"这一问的实战意义：

多加一个维度，状态数直接翻倍 —— 而这里的翻倍是【完全没必要】的。

那什么时候必须加维度？

把规则改成"偷完必须休息一天"（冷冻期）：

昨天的状态	今天能偷吗
昨天偷了	❌ 不能（要休息）
昨天没偷	✅ 能

这时 f(i-1) 这个数就【分不出】两种情况了 —— 因为它只记录了"最大金额"，没记录"昨天偷没偷"。

状态必须升级成：

$$f(i, \text{昨天偷没偷})$$

这两个例子的对照非常重要：

"需不需要加维度"不是靠感觉，而是靠第一问： "两个状态相同的局面，未来会不会不同？"

普通打家劫舍：只要金额相同，明天能不能偷都一样 → 不用加

有冷冻期：金额相同，但"昨天偷了"和"昨天没偷"会导致今天的选择不同 → 必须加

15.1 节那个满减券的坑，也是同一条：

"剩余订单金额"看起来是个好状态，但它【分不出】"哪些券已经用过了"。 而"还能用哪些券"恰恰取决于这个。

所以那个问题的状态里，必须包含"券的使用情况" —— 这也是 14.3 练习 14.3.4 说"200 张券会状态爆炸"的原因： 2^200 种组合，没法当状态。

七、练习

练习 15.2.1（定义状态）对下面的问题，写出状态定义、转移方程和边界条件（不用写代码）：

(a) 数字三角形：一个三角形阵列，从顶部走到底部，每次只能走向左下方或右下方的相邻数字，求路径上数字之和的最大值。 (b) 零钱兑换：给定若干种面额的硬币（每种无限多），凑出金额 $X$ 所需的最少硬币数。

练习 15.2.2（自检）下面几个状态定义，用四个自检问题判断它们是否成立：

(a) LIS 里定义 f[i] = 前 i 个元素的最长递增子序列长度 (b) 零钱兑换里定义 f(x) = 凑出金额 x 所需的最少硬币数 (c) 一个"网格里从左上走到右下，求最大路径和"的问题，定义 f(r, c) = 走到 (r,c) 的最大路径和

练习 15.2.3（打家劫舍的变体）把打家劫舍的规则改成"偷完必须休息一天"（冷冻期）：

(a) 状态该怎么定义？为什么原来的一维状态不够？ (b) 写出转移方程。 (c) 状态总数是多少？比原来多了几倍？

练习 15.2.4（判断）判断对错并说明理由： (a) 状态维度越多，DP 越准确。 (b) LIS 的答案就是 dp[n-1]。 (c) 转移方程就是把"最后一步"的所有可能列出来。 (d) 只要状态定义对了，转移方程就一定能写出来。

练习 15.2.5（挑战·LIS 的第二种状态） LIS 还有一个复杂度更低的解法（$O(n \log n)$），它用的状态定义完全不同：

tails[k] = 所有长度为 k+1 的递增子序列中，【结尾最小的那个值】

(a) 为什么"结尾最小的那个"是最值得保留的信息？（提示：想想第 1 问） (b) tails 这个数组有什么特殊性质？（提示：它是不是递增的？） (c) 有了递增性之后，可以用什么算法来更新它？复杂度是多少？

八、练习答案

15.2.1

(a) 数字三角形

状态定义：

$$f(r, c) = \text{从顶端走到第 } r \text{ 行第 } c \text{ 列的最大路径和}$$

四问自检：

够吗？ 位置 $(r,c)$ 决定了一切，怎么走来的不重要 ✓
多吗？ 每个格子对应一个真实局面 ✓
算得动吗？ 行数 × 列数，二维数组 ✓
转移只看它吗？ 是 ✓

转移方程（枚举最后一步：从左上还是右上走过来的）：

$$f(r, c) = \max\big(f(r-1, c-1),\ f(r-1, c)\big) + a_{r,c}$$

边界：

$$f(0, 0) = a_{0,0}$$

答案：$\max_c f(\text{最后一行}, c)$ —— 又是"最后一层取 max"，和 LIS 同一个道理。

为什么不是 f(最后一行, 0)？ 因为 $f(r,c)$ 的含义是"走到 $(r,c)$"， 而终点可以是最后一行的任意一列。

(b) 零钱兑换

状态定义：

$$f(x) = \text{凑出金额 } x \text{ 所需的最少硬币数}$$

转移方程（枚举最后一步：最后一枚硬币是哪种面额）：

$$f(x) = \min_{c \le x}\big(f(x - c) + 1\big)$$

边界：

$$f(0) = 0, \qquad f(\text{凑不出}) = \infty$$

答案：$f(X)$（如果它是 $\infty$，说明凑不出）。

这个转移方程在 14.1 节出现过 —— 那里用它作为"贪心的对照"。 注意它和 LIS 的区别：LIS 要 max，这里要 min， 但"枚举最后一步"的手法完全一样。

15.2.2

小题	成立吗	分析
(a)	❌ 不成立	第 1 问失败：两个"前 $i$ 个"的 LIS 长度相同，但结尾不同的局面，未来不同。实测正确率只有 37.4%。
(b)	✅ 成立	四问都过：金额 $x$ 完全决定后续；每个 $x$ 一个状态；状态数 $X+1$；转移只依赖更小的金额。
(c)	✅ 成立	四问都过。注意"怎么走到 $(r,c)$"被正确地忽略了 —— 因为题目只要求"路径和"，不要求"路径本身"。

(c) 有个前提值得点出：如果题目改成"求路径和的【最大值】并且要输出路径"， 那 f(r,c) 就不够了 —— 因为你还得能还原出路径。

解决办法是再加一个 prev 数组记录"从哪来"（12.3 节 BFS 的 prev 就是这个套路）， 而不是把路径塞进状态里 —— 后者会让状态数爆炸。

15.2.3

(a) 状态必须包含"昨天偷没偷"。

为什么一维不够？ 因为同样是"前 $i$ 家偷了 12 元"这个状态，可能来自两种不同的历史：

历史	昨天（第 $i$ 家）偷了吗	今天能偷吗
历史 A	偷了	❌ 不能（要休息）
历史 B	没偷	✅ 能

第 1 问失败：两个状态相同（都是"前 $i$ 家 12 元"）的局面，未来不同。

(b) 转移方程

$$f(i, 0) = \max\big(f(i-1, 0),\ f(i-1, 1)\big)$$

$$f(i, 1) = f(i-1, 0) + a_i$$

含义：

$f(i, 0)$：第 $i$ 家不偷 → 昨天偷没偷都行，取最大的
$f(i, 1)$：第 $i$ 家偷了 → 昨天必须没偷 → 只能从 $f(i-1, 0)$ 来

答案：$\max\big(f(n-1, 0),\ f(n-1, 1)\big)$

(c) 状态总数翻了一倍。

	状态数
原来的打家劫舍	$n + 1$
带冷冻期	$2(n + 1)$

只多了一倍，还算能接受 —— 但如果规则再复杂一点（比如"连续偷两天要休息三天"）， 状态就得记住"最近几天的偷窃记录"，维度会继续涨。

这正是第 3 问（"算得动吗"）要盯住的东西： 每加一个维度，状态数是【乘法级】增长，不是加法级。

15.2.4

小题	判断	理由
(a)	❌ 错	维度够用就行，多了是浪费。本节实测：打家劫舍的二维版和一维版结果完全一样（3000 组零不一致），但二维版的状态数翻倍。
(b)	❌ 错	答案是 $\max_i dp[i]$。因为 `dp[i]` 的含义是"以 $a_i$ 结尾"，而最长的那条不一定以最后一个元素结尾。
(c)	✅ 对	这就是转移方程的通用推导手法：列出"最后一步"的所有可能，每种情况对应一个更小的状态。
(d)	❌ 错	状态对了但转移写不出来，是完全可能的。比如某些问题的最优解无法由子问题的最优解拼出来（14.1 说的"最优子结构"不成立）——那种问题就不适合 DP。

(d) 指向的是 14.1 节的第一个前提：最优子结构。

DP 需要两个前提：最优子结构 + 重叠子问题（15.1）。 本节讲的是"怎么把这两个前提落地成状态和方程"，但前提本身不成立的话，状态怎么定都没用。

15.2.5

(a) 因为"结尾越小，后面能接上的机会越多"。

回到第 1 问："长度为 $k+1$ 的递增子序列"这个局面，未来取决于什么？

只取决于它的结尾值 —— 结尾越小，后面能接的数就越多。

所以对于同一个长度 $k+1$，我们只需要保留【结尾最小的那个】—— 它在任何情况下都不比别的差。

这就是"状态压缩"的本质：当同一个"规模"下有多个局面时，如果其中一个【支配】了其他所有局面，就只留它一个。

这也解释了为什么 LIS 的 $O(n^2)$ 解法里 dp[i] 要带"以 $a_i$ 结尾" —— 那里的状态是"以谁结尾"；而这里的 tails[k] 是"长度为 $k+1$ 时结尾最小是多少"。 同一个问题，两种状态定义，复杂度差一个 $\log$。

(b) tails 是严格递增的。

为什么？ 用反证法：

假设 $tails[k-1] \ge tails[k]$。

tails[k] 是某个长度为 $k+1$ 的递增子序列的结尾。 把那个子序列的最后一个元素去掉，就得到了一个长度为 $k$ 的递增子序列，它的结尾 $< tails[k] \le tails[k-1]$。

但 tails[k-1] 的定义是"长度为 $k$ 的子序列里结尾【最小】的" —— 矛盾 ✓

所以 tails 一定严格递增。

(c) 可以用二分查找，复杂度 $O(n \log n)$。

处理每个 $a_i$ 时：

在 tails 里二分找到第一个 $\ge a_i$ 的位置，把它替换成 $a_i$ （如果找不到，就追加到末尾 —— 说明找到了更长的子序列）。

每一步是 $O(\log n)$，一共 $n$ 步 → 总计 $O(n \log n)$。

这个解法是 15.3 节的内容（那里会给完整实现和实测）。 这里提前放出来，是为了说明一件事：

同一个问题，状态定义不同，复杂度可能差一个量级。

"状态定义"不是走个形式 —— 它是 DP 里最值钱的一步。

九、常见错误

误区	纠正
状态定义"差不多就行"	差一个词就错。实测：LIS 里"前 $i$ 个"和"以 $a_i$ 结尾"只差一个词，正确率 37.4% vs 100%。
认为"维度越多越保险"	多加一个维度，状态数是乘法级增长。实测：打家劫舍的二维版和一维版结果完全一样（3000 组零不一致），但状态数翻倍。
LIS 的答案取 `dp[n-1]`	要取 $\max_i dp[i]$。因为 `dp[i]` 是"以 $a_i$ 结尾"，最长的未必以最后一个元素结尾。
状态里塞进"整个历史"	不加思考地把所有信息都放进状态，会导致状态爆炸。正确做法是问第 1 问："哪些信息真的会改变未来？"
只检查"状态对不对"，不检查"转移写不写得出"	状态对了但转移写不出，说明【最优子结构】不成立，那这个问题就不适合 DP（14.1）。
认为状态定义是"形式主义"	它是 DP 里最值钱的一步。同一个 LIS，状态定义换一种，复杂度从 $O(n^2)$ 降到 $O(n\log n)$（练习 15.2.5）。

十、本节总结

状态 = "决定未来的那一小撮信息" —— 怎么走来的不重要，重要的是"还剩什么"。
那条判据（本节最重要的一句话）：两个局面状态相同 ⟹ 后续的最优解也相同。
四个自检问题：够吗（漏信息）、多吗（白算）、算得动吗（乘法级爆炸）、转移只看它吗（同 15.1 的缓存合法性）。
转移方程的推导手法：枚举"最后一步"的所有可能。爬楼梯、打家劫舍、LIS 三个方程形状完全一样，区别只在"更小的状态是谁"。
实测一（LIS）：f[i] = 前 i 个元素的 LIS 长度 丢掉了"结尾是什么"，在 [4,5,1,2,3] 上给出 4（正确是 3）； 3000 组随机数据上正确率只有 37.4%，而正确的定义（以 $a_i$ 结尾）是 100%。
实测二（打家劫舍）：一维状态 $f(i)$ 和二维状态 $f(i, \text{偷没偷})$ 结果完全一致（3000 组零不一致） —— "看起来需要的信息"不一定真的需要，要用第 1 问去检验。
但改一个字就要加维度：加"冷冻期"后，"昨天偷没偷"就必须进状态 —— 因为 $f(i-1)$ 分不出两种情况。 15.1 那个满减券的坑（"剩余金额"不够，还得知道"哪些券用了"）是同一回事。
状态定义是 DP 里最值钱的一步：LIS 换一种状态定义，复杂度能从 $O(n^2)$ 降到 $O(n\log n)$。

下一节衔接：本节把"状态"和"转移"这两步讲清楚了，但用的都是小例子。

15.3 节上两个真正的经典题：

0/1 背包 —— 14.3 节那个"贪心近似比无界"的问题，现在给它补上 DP 解法
最长递增子序列 —— 练习 15.2.5 预告的那个 $O(n\log n)$ 解法，完整实现 + 实测

这两道题还会带出 DP 里几个绕不开的细节： 为什么背包要倒着遍历？二维数组能不能压成一维？tails 的二分到底在找什么？

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "15.2",
  "title": "状态定义与转移方程",
  "covered": [
    "状态的定义：「决定未来的那一小撮信息」及其形式化判据",
    "四个自检问题（够不够 / 多不多 / 算得动吗 / 转移只看它吗）",
    "转移方程的通用推导手法：枚举最后一步",
    "例题一：爬楼梯的完整三步推导（状态 -> 转移 -> 边界）",
    "实测一：LIS 的错误状态定义（前 i 个）vs 正确定义（以 a[i] 结尾），反例 [4,5,1,2,3]",
    "实测一的对拍：错误版 37.4% vs 正确版 100%（3000 组）",
    "「答案是 max_i dp[i] 而不是 dp[n-1]」的由来",
    "实测二：打家劫舍的一维 vs 二维状态定义，3000 组零不一致",
    "「什么时候必须加维度」的判据（冷冻期变体）",
    "满减券的状态定义问题（呼应 15.1 练习 15.1.5）",
    "LIS 的 O(n log n) 状态定义（tails 数组）与二分更新的原理"
  ],
  "unresolved": [
    "0/1 背包的 DP 实现留到 15.3",
    "LIS 的 O(n log n) 完整实现与实测留到 15.3",
    "空间优化（滚动数组）留到 15.4",
    "数字三角形的完整代码未给出（只要求写状态与方程）"
  ],
  "canonical_terms": {
    "状态（State）": "求解过程中决定未来的那一小撮信息；两个局面状态相同则后续最优解相同",
    "状态转移方程（State Transition）": "描述当前状态由哪些更小的状态推出的式子；由「枚举最后一步」推导",
    "最优子结构（Optimal Substructure）": "问题的最优解由子问题的最优解拼成（14.1 已引入，本节再次使用）"
  },
  "symbols_units": {
    "f(i) / dp[i]": "第 i 个状态的值",
    "a_i": "数组第 i 个元素",
    "tails[k]": "所有长度为 k+1 的递增子序列中结尾最小的值"
  },
  "assumptions": [
    "读者已掌握 15.1 的记忆化与重叠子问题",
    "读者理解 14.1 的两个前提（最优子结构与贪心选择性质）",
    "LIS 采用严格递增的定义（相等元素不算递增）"
  ],
  "word_count_actual": 3945,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch15/Sec152/",
    "实验一：反例 [4,5,1,2,3] 上错误版给 4、正确版给 3、暴力枚举给 3，均为实测",
    "实验一的对拍：3000 组随机数组（seed=20260918，长度 5~12，元素 1~9）错误版 1123/3000、正确版 3000/3000，为实测",
    "实验二：例子 [2,7,9,3,1] 三种解法都得 12；3000 组随机数据上两种状态定义零不一致，为实测",
    "术语写法与 glossary.md 一致（状态转移方程、记忆化、动态规划）"
  ],
  "known_issues": [
    "实验一的「错误状态定义」需要人工构造：初版想用相邻元素比较的朴素递推，但在 [1,5,2,3,4]、[3,1,2,3,4] 等多个例子上碰巧都对 —— 最终找到 [4,5,1,2,3]（数组先升后降再升）才稳定暴露问题，并在正文里把这个反例逐步展开",
    "初版把「四个自检问题」设计成并列的四条，写完发现第 1 问和第 4 问高度重叠 —— 改为在正文中明确点出「两者是同一要求的两面（状态必须是未来的充分摘要）」，避免读者当成两件事记",
    "练习 15.2.5 提前放出了 LIS 的 O(n log n) 解法，与 15.3 节内容有重叠 —— 已在正文和状态卡的 unresolved 里明确标注「完整实现与实测留到 15.3」，本节只讲状态定义层面的原理"
  ],
  "next": "15.3 经典题型：背包与最长递增子序列"
}

15.2　状态定义与转移方程