# 0026 · 序列与区间的状态设计 · 参考解

这一课练四件事，都是「**先把状态定义写出来，再写代码**」：

| 任务 | 文件 | 要交的东西 | 状态定义 |
| --- | --- | --- | --- |
| 1 · 最长递增子序列 | `task1_lis.py` | `lis_dp` / `lis_bisect` / `lis_recover` | $dp[i]$ = **以 $a_i$ 结尾**的最长递增子序列长度 |
| 2 · 最长公共子序列 | `task2_lcs.py` | `lcs` / `table_shape` | $dp[i][j]$ = s 的**前 i 个**与 t 的**前 j 个**的 LCS 长度 |
| 3 · 最长回文子序列 | `task3_palindrome.py` | `lps` / `lps_brute` | $dp[i][j]$ = $s[i..j]$ 这段里的最长回文子序列长度 |
| 4 · 石子合并 | `task4_stone.py` | `stone_dp` / `stone_desc` / `stone_brute` | $dp[i][j]$ = 把第 i 堆到第 j 堆合成一堆的最小代价 |

把这一份里的文件拷进你的任务目录就能直接跑（`tools.py` 与 `run_tests.py` 两侧内容完全相同）：

```text
py run_tests.py        # 在 lab/solutions/0026-dp-sequence-interval/ 目录里直接跑
```

这一课真正要拿走的一句话：**上一课的背包，状态是题目递给你的（容量）；这一课的状态得自己设计。**
「前 $i$ 个的最大 XXX」和「**以第 $i$ 个结尾**的最大 XXX」看着差不多，选错一句就写不出转移方程。

## 逐题：为什么这么写

### 任务 1 · LIS：三种东西，三个接口

`lis_dp` 交回 `(max(dp), dp)`——**答案是 `max(dp)` 而不是 `dp[n-1]`**。
最长的那条不一定结尾在最后一个位置，这里 `dp[6] = dp[7] = 4` 恰好并列，很容易蒙对；
换一组数据（课件那句话的用意就在这）`dp[-1]` 就比 `max(dp)` 小了。

`lis_bisect` 交回 `(len(tails), tails)`，`tails[k]` 是「所有长度为 $k+1$ 的递增子序列里，
**结尾最小的那个值**」。要维护它的理由很实在：结尾越小，后面越容易接得上，
所以每个长度只要留最小的那个结尾就够了。

**`tails` 本身不是一条递增子序列**——这是这一课最值得记住的一件事：

```text
序列                     [10, 9, 2, 5, 3, 7, 101, 18]
tails（记账数组）          [2, 3, 7, 18]        长度 4
一条真正的最长递增子序列    [2, 5, 7, 101]       长度 4
```

长度一样，元素完全对不上。要长度就用二分版；**要那条子序列本身，就得用 $O(n^2)$ 的 dp 加一个
`prev` 数组回溯**（`lis_recover` 干的就是这件事）。

有一处值得说清，免得被自己骗过：在这组特定数据上 `[2, 3, 7, 18]` **碰巧也是**原序列的合法子序列
（下标 2、4、5、7）。所以「是不是子序列」这个检查**不是**区分器——真正的区分器是
「恢复出的序列与判分要的那一条**逐项相同**」（`[2, 5, 7, 101]`）。

### 任务 2 · LCS：把表打印出来是最省事的自查

$dp[i][j]$ 的依赖方向是**左、上、左上**——这三个方向天然对应逐行逐列填，
所以 LCS **不需要**操心枚举顺序。第一行与第一列全是 0（空串配任何串，公共子序列长度都是 0）。

表建对没对，一眼就能看出来：形状是 `(len(s)+1) × (len(t)+1)`，第一行第一列的 0 共
`len(t)+1 + len(s)+1 - 1 = 13` 个，答案在**右下角** `dp[n][m]`。

这份练习要写 `table_shape`，就是把这件自查变成一个数字：`(行数, 列数, 两条边上的 0 的个数)`。

### 任务 3 · 最长回文子序列：区间 DP 的第一条规矩

$dp[i][j]$ 依赖的是 **$dp[i+1][\cdot]$ 与 $dp[\cdot][j-1]$——比它更小的区间**。
所以枚举顺序不能随便：**必须先算短的区间，再算长的**。

```python
for length in range(2, n + 1):          # 关键就是这一行
    for i in range(0, n - length + 1):
        j = i + length - 1
```

这正是区间 DP 跟任务 2 最大的不同：LCS 的依赖方向天然对应双层循环，
而这里**必须显式按区间长度枚举**。

### 任务 4 · 石子合并：断点枚举 + 区间和；写反顺序 = 答案偏小

转移要在**最后那一次合并断在哪里**上枚举：

$$dp[i][j] = \min_{i \le k < j}\bigl(dp[i][k] + dp[k+1][j]\bigr) + \text{sum}(i..j)$$

末尾那个 $\text{sum}(i..j)$ 是**这次合并本身的代价**：不管前面怎么合，第 $i$ 到第 $j$ 堆
合成一堆，这一下必然要把区间内所有石子清点一遍。用前缀和 $O(1)$ 拿到。

`stone_desc` 是**故意把长度枚举写反**的那一版（`range(n, 1, -1)`），它给出的答案是错的：

```text
[4, 1, 2, 3]        19  →  10
[3, 4, 5, 6, 7]     57  →  25
[1, 2, 3, 4, 5, 6]  51  →  21
```

**偏小，而且小得离谱。** 原因不绕：长度从大到小枚举时，算长区间要用到的短区间**还没被算过**，
`dp[i][k]` 与 `dp[k+1][j]` 都还是初始的 0，于是转移只加上了「这次合并的代价」，
**前面所有合并的代价全被漏掉了**，区间越长漏得越多。

判分自己拿 200 组随机数据走过一遍（1~7 堆、每堆 1~20，`random.seed(9)`，与脚本同一造法）：
**从小到大错 0 组，从大到小错 137 组**。在判分另外自造的 109 组上复核，
从大到小有 78 组给出偏小的答案（另有 31 组因为堆数少／数值巧合而恰好一样）——
**「写反不等于每组都错，但只要错就一定是偏小」**。

对照着记：上一课背包写错方向时答案是**偏大**的（同一件物品被拿了多次）；
这里写错顺序是**偏小**的。**答案偏离的方向会告诉你错在哪一类**——
看到答案不对，先问一句「它错向了哪边」。

## 常见错法（判分逐条盯着）

| 错法 | 症状 | 判分读的那一行 |
| --- | --- | --- |
| `lis_dp` 交回 `dp[-1]` 而不是 `max(dp)` | 换一组数据就偏小 | `LIS 长度（DP 版）` / `计数 LIS 长度` |
| `lis_bisect` 用 `bisect_right` | 全相同元素 `[5,5,5,5]` 上得到 4，不是 1 | `全相同元素 两版长度` 期望 `1 1` |
| 把 `tails` 当成「那条子序列」交回来当答案 | 长度对、元素对不上 | `tails 与恢复出的子序列相同吗` 期望 `False`；`恢复出的就是判分要的那一条` 期望 `True` |
| `lis_recover` 只写 `dp` 不记 `prev` | 恢复不出东西，或长度对不上 | `恢复出的长度等于 LIS 长度`、探针里「长度不对的组数」 |
| LCS 表建成 `n × m`（少那一圈 0） | 第一行第一列不是全 0、右下角错位 | `第一行第一列 全是0`、`计数 dp 表 行数/列数` |
| LCS 比的是 `s[i]` 与 `t[j]` 而不是 `s[i-1]` 与 `t[j-1]` | 表整体错位一格 | 判分**逐格**对照打印出来的那张表 |
| 区间 DP 用双层 `for i / for j` 直接填 | 长区间用到的短区间还是 0，答案偏小 | `lps` 四组期望值、`stone_dp` 三组期望值 |
| 石子合并写了长度顺序但**没加区间和** | 答案偏小且量级不对 | `计数 石子[…] 从小到大` 期望 19 / 57 / 51 |
| `stone_brute` 用列表当 `lru_cache` 的键 | `TypeError: unhashable type: 'list'` | 脚本直接报错退出（判分会指名 TODO 3） |
| 对外接口乱改（函数名、`print` 行、`show_count` 编号） | 判分「没看到某一行」 | 所有 `没看到「…」` 的 FAIL |

## 判分在读什么

`run_tests.py` 分两路，缺一不可：

1. **跑任务脚本、读它自己打印的行**（这一路是主要证据）。
   固定格式四种，由 `tools.py` 生成：

   ```text
   计数 NN <标签> <值>          整数 或 True/False
   耗时 NN <标签> <n=…> <秒数> 秒     六位小数
   <标签> <值>
   <标签> <值1> <值2>
   ```

   判分**按标签找行**（不按编号）——标签里写着是这一组数据、是哪个方向。
   留白版会把这些行**原样打出来**，只是值是占位的（`0` / `[]` / `-1` / `0.000000`），
   所以「看得见的格式」和参考解完全一致。

2. **另起探针进程 `import` 学生的函数，用判分自己造的数据试**（这一路是独立证据）。
   探针的数据与脚本那几批**刻意不同**（判分用 `seed(1011)` / `seed(2027)` 等，
   脚本用 `seed(11)` / `seed(12)`）：**只写 print 不写实现拿不到 PASS**。

判分自己另有一份参照实现（`model_lis_dp` / `model_lis_bisect` / `model_lis_sequence` /
`model_lcs` / `model_lps` / `model_lps_brute` / `model_stone` / `model_stone_brute`），
期望值都是用它在**判分自己砌的同一批数据**上现算的，不是抄来的常数。

**判分看趋势不看常数**：秒数每次运行都会浮动（课件自己也写了第二次跑就不一样），
所以耗时那一列只要求「二分版每一档都比 DP 版快」「规模翻四倍时 DP 版涨得更多」
「二分版在最大一档更快」，以及几处留了 25% 噪声带的比较，**绝不核对具体秒数**。
判分里核对精确值的是那些**确定量**：19 / 57 / 51、10 / 25 / 21、137 组错、
500 组不一致 0 组、4 / 3 / 5 / 4、13 个 0、8×7 的表、`[2, 3, 7, 18]` 与 `[2, 5, 7, 101]`。