2026年秋第8次课

状态表建好之后，答案就一定在表里吗？什么情况下连表都不该建？

第6次课从打家劫舍、矩阵连乘与最大子数组和里提炼出状态设计的五问，上一次课比较了使用最小花费爬楼梯的一维状态与矩阵连乘的二维区间状态，重点回答「状态需要几个下标、按什么顺序算」。本课沿这条线再走一步：状态定义只是中间产物，还要判断题目是否存在有限答案、状态值是不是题目要的答案，以及压缩状态之后哪些信息会永久丢失。

两道题分别是买包子和最长公共子序列。前者的答案是「凑不出的正整数个数」，既不是某个格子的值，也可能根本没有有限值；后者的答案恰好是右下角一格，但要输出具体子序列，还得从表格里反向恢复决策。两题都不难写出 dp 数组，难的是说清「从状态到答案」中间那几步。

本讲义按两个题目串联课堂思路，完整 Python 实现、逐步状态表、易错点与课堂练习见对应链接。课堂先判定、再建表、最后加工答案；不把背下某个模板当作理解算法的替代。

学习目标

本课需要回答的五个问题

• 题目要的答案是什么？ 是某个状态值、对整张表的统计，还是一个需要恢复的具体方案？
• 有没有不该建表的分支？ 说明判据，并解释为什么扩大数组也救不了这个分支。
• 状态里存的是什么？ 布尔值、长度还是成本？据此写出边界与转移，并说明依据。
• 枚举范围与递推顺序怎样保证不漏不重？ 分别指出内层递增、连续窗口与按行填表各自在防什么错。
• 压缩状态丢了什么？ 区分「求最优值」与「输出方案」，说明空间优化后哪些任务不再可行。

课后应能独立写出两题的状态、边界、转移、答案位置与复杂度，能用小规模过程表核对结果，并说清 INF 分支、连续窗口与反向回溯分别补上了哪一步。

本课路线

顺序	题目与材料入口	课堂核心问题	状态 → 答案
1	买包子	什么时候凑不出的数有无穷多个？布尔可达性怎样变成「个数」？	布尔表 → 找连续窗口 → 统计缺口
2	最长公共子序列	末字符相等与不等时分别依赖哪些格子？长度之外还能读出什么？	长度表 → 右下角取值 / 反向回溯方案

两题依次推进：先处理「答案可能根本不存在有限值、状态值也不是答案」的情形，再回到「答案就在表里、但方案不在表里」的情形。共同结论是：状态回答的是「子问题怎么样」，题目要的往往是「整张表说明了什么」。

环节	时间	内容	课堂产出
题意热身	10′	读准「个数」「INF」「子序列不连续」，辨析三处常见误读	写出两题的输入输出约定
精讲一	25′	买包子：gcd 前置判定、完全背包布尔状态、内层递增、连续窗口	手算 [4,5] 的可达数轴与答案 6
现场编码	15′	主实现与竞赛简写版对照，跑通 [4,5]、[4,6]、[6,10,15]	说清 10000 的来源
精讲二	25′	最长公共子序列：双序列前缀状态、两类转移、6×4 状态表、回溯	填出 dp[5][3] = 3，读出 "ace"
课堂核对	10′	完成下方五个任务，重点检查判定分支与压缩代价	口头解释错误写法
复盘小结	5′	方法比较表、检查顺序、课后实践	形成一页总结

按 2 学时 90 分钟组织，沿用第7次课口径；若为 3 学时，可把「现场编码」延长为两版实现的完整对照，并增加滚动数组与回溯的独立上机。两题课堂上都按「判定 → 建表 → 加工答案」三步推进。

题目串联

一、买包子：先判定答案是否有限，再谈动态规划

题目材料与 Python 实现：买包子。

先把题意读成「计数 + 分支」

包子铺有 $N$ 种蒸笼，第 $i$ 种恰好装 $A_i$ 个，每种可以取无限多笼。给定 $1\le N\le100$、$1\le A_i\le100$，统计有多少个正整数数目凑不出来；若有无穷多个，输出 INF。

样例 2 4 5 → 6 与 2 4 6 → INF 里有三处容易读错：第一个数是 $N$ 而不是第一种容量；答案是凑不出的数的个数，样例中最大的凑不出的数是 11，答案却是 6；INF 是合法输出，不是异常。它与买不到的数字（求最大的凑不出的数）和零钱兑换（求凑出金额的组合数）都不是同一问。

第一步：用整体最大公约数决定要不要建表

记 $g=\gcd(A_1,\dots,A_N)$。若 $g>1$，任何组合 $\sum k_i A_i$ 都是 $g$ 的倍数，所有非 $g$ 倍数的正整数都凑不出，答案是 INF；只有 $g=1$ 时，由裴蜀定理才保证凑不出的数只有有限个，值得进入动态规划。

这一步必须放在建表之前。对 $g>1$ 的用例，无论数组开到多大，统计出来的都只是「上界以内的假答案」：[4,6] 的 $g=2$，所有奇数都凑不出；[7] 的 $g=7$，除 7 的倍数外全都凑不出。

还要用整体 $\gcd$，不能用「两两互质」代替。[6,10,15] 的两两 $\gcd$ 分别是 2、3、5，没有一个等于 1，但三者整体的 $\gcd$ 是 1，答案是有限值 15。把整体判定写成两两判定会误输出 INF。

第二步：布尔可达状态与完全背包

定义布尔状态 $dp[x]$：只用已经处理过的容量，能否恰好凑出 $x$ 个包子。

$$dp[0]=\text{True},\qquad dp[x]=\text{False}\ (x\ge1\text{，初始})$$

依次把每种容量 $a$ 加入可选集合，对 $a\le x\le L$ 执行：

$$dp[x]\leftarrow dp[x]\ \text{or}\ dp[x-a].$$

$x$ 必须从小到大遍历。这样 dp[x-a] 在本轮可能刚被更新，恰好表示同一容量被取用了多次；若改成从大到小，每种容量最多用一次，模型退化成01背包问题。以 [4,5] 为例，$10=5+5$ 要求本轮的 $x=5$ 先置真，$14=9+5$ 同理；倒序处理 $x=10$ 时 dp[5] 仍为假，10 会被误判为凑不出。

第三步：状态表填到哪、答案怎么取

以主示例 [4,5] 为例，1 表示可凑出、0 表示凑不出：

阶段	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
只用容量 4	1	0	0	0	1	0	0	0	1	0	0	0	1	0	0	0	1
加入容量 5	1	0	0	0	1	1	0	0	1	1	1	0	1	1	1	1	1

dp[0]=1 只是「一笼都不选」的起点，不参与答案统计。加入容量 5 后新增的可达数包括 $5$、$9$、$10$、$13$、$14$、$15$，其中 $10=5+5$ 与 $14=9+5$ 是内层递增的直接证据。

停止条件

设 $m=\min(A_i)$。若从 $t$ 开始出现连续 $m$ 个可达整数 $t,t+1,\dots,t+m-1$，则任意 $x\ge t$ 都可写成其中某一个再加上若干个 $m$，因而此后全部可达。

本例 $m=4$，最早连续 4 个可达数出现在 $12,13,14,15$，即 $t=12$。只需检查 $1$ 到 $11$，凑不出的是 $1,2,3,6,7,11$，共 6 个，与样例一致。注意答案不是状态表里某一格，而是对整张表的一次统计。

枚举上界取 $L=\max(A_i)^2$：在模 $m$ 的每个余数类里，最小可达数可视为 $m$ 个余数节点上的最短路，最多经过 $m-1$ 条边、每边权不超过 $\max(A_i)$，故小于 $m\cdot\max(A_i)\le L$。当 $A_i\le100$ 时 $L\le10000$，这正是竞赛简写版直接写 10000 的来历——它是由约束推出的枚举上界，不是题目给出的输入上限。

按去重后的容量种数 $N$、$M=\max(A_i)$、$L=M^2$ 计：主实现时间 $O(NL)$、辅助空间 $O(L)$；仅走 INF 分支时，求 $\gcd$ 需 $O(N\log M)$、空间 $O(1)$，完全不进入填表。

衔接最长公共子序列： 这里状态是布尔值，答案是对整张表的二次统计，而且要先靠数论排除「答案无穷」的情况。如果状态本身存的是长度、答案恰好是右下角一格，是否就万事大吉？

二、最长公共子序列：答案在右下角，方案不在表里

题目材料与 Python 实现：最长公共子序列。

先把「子序列」与「子串」「前缀」分开

给定两个字符串 text1、text2，长度 $m,n\le1000$，只含小写字母，求最长公共子序列的长度。子序列允许删除若干字符，但保持相对顺序、不要求连续："ace" 是 "abcde" 的子序列，"aec" 不是。

这与最长公共前缀（从开头起连续相同的一段）名字相近但问题不同；若把「末字符不等」时的状态直接置 0，求的其实是最长公共子串，因为不允许跳过字符就断掉了历史长度。

定义双序列前缀状态

定义 $dp[i][j]$：text1 的前 $i$ 个字符与 text2 的前 $j$ 个字符的最长公共子序列长度。 它不要求一定选 text1[i-1] 或 text2[j-1]，正是这一点让「跳过某个字符」能被表达。

任一前缀为空时结果为 0，因此用一行一列哨兵统一处理：

$$dp[0][j]=0,\qquad dp[i][0]=0.$$

状态表大小为 $(m+1)\times(n+1)$，最终答案为 $dp[m][n]$。

根据末字符是否相等推导两类转移

记 $s=text1[i-1]$、$t=text2[j-1]$：

$$dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & s=t,\\[4pt] \max\bigl(dp[i-1][j],\ dp[i][j-1]\bigr), & s\ne t. \end{cases}$$

相等时，一定存在包含这个公共末字符的最优解，去掉它后问题变成两个都缩短一位的前缀，因此两个下标同时减 1，不是只减列下标。不等时，最优解不可能同时用到这两个末字符，至少要跳过其中一个；dp[i-1][j] 表示跳过 text1 的末字符，dp[i][j-1] 表示跳过 text2 的末字符，两个方向都必须考虑。

反例 text1 = "ab"、text2 = "cab"，在计算 $dp[2][2]$（"ab" 与 "ca"）时末字符 $b\ne a$：

$dp[i][j]$	$j=0$	$j=1$（c）	$j=2$（a）	$j=3$（b）
$i=0$	0	0	0	0
$i=1$（a）	0	0	1	1
$i=2$（b）	0	0	1	2

此时 $dp[1][2]=1$、$dp[2][1]=0$，若只取后者会把该格误算成 0，进而影响后面的格子；正确答案是 2，对应 "ab"。

主示例的完整状态表与答案

text1 = "abcde"、text2 = "ace"：

$dp[i][j]$	$j=0$（空）	$j=1$（a）	$j=2$（c）	$j=3$（e）
$i=0$（空）	0	0	0	0
$i=1$（a）	0	1	1	1
$i=2$（b）	0	1	1	1
$i=3$（c）	0	1	2	2
$i=4$（d）	0	1	2	2
$i=5$（e）	0	1	2	3

关键格子：$dp[3][2]$ 遇到 c == c，取 $dp[2][1]+1=2$；$dp[3][3]$ 遇到 c != e，取 $\max(1,2)=2$；$dp[5][3]$ 遇到 e == e，取 $dp[4][2]+1=3$。$dp$ 值沿行、沿列都不会下降，因为扩大前缀只会增加可选字符。

答案 $dp[5][3]=3$ 可以直接读出，但表里只保存长度，并没有保存 "ace" 这三个字符。要输出一种具体方案，需从右下角反向追踪：相等时收录字符并走到 $(i-1,j-1)$，不等时朝 $dp$ 值较大的相邻格走。

当前位置	比较	决策	下一位置
$(5,3)$	e == e	收录 e	$(4,2)$
$(4,2)$	d != c	$dp[3][2]=2\ge dp[4][1]=1$，跳过 d	$(3,2)$
$(3,2)$	c == c	收录 c	$(2,1)$
$(2,1)$	b != a	$dp[1][1]=1\ge dp[2][0]=0$，跳过 b	$(1,1)$
$(1,1)$	a == a	收录 a	$(0,0)$

逆序排列得到 "ace"。若两处候选相等时改走另一方向，可能得到别的最长公共子序列，长度仍是 3。

压缩空间会丢掉什么

计算第 $i$ 行只需要第 $i-1$ 行以及本行已经算出的左侧格子，因此可用 prev、curr 两行数组：相等时 curr[j] = prev[j-1] + 1，不等时 curr[j] = max(prev[j], curr[j-1])，其中 curr[j-1] 是本行的新值，不能写成 prev[j-1]；每行算完交换两行，返回 prev[n]。

本例各行依次为 [0,1,1,1]、[0,1,1,1]、[0,1,2,2]、[0,1,2,2]、[0,1,2,3]，与完整状态表逐行一致。压缩把辅助空间从 $O(mn)$ 降到 $O(n)$，但要计算的格子数一个也没少，时间仍是 $O(mn)$；更关键的是，只剩两行就无法反向恢复历史决策，输出方案需要 $O(mn)$ 的完整表或等价的决策记录。

与矩阵连乘对照：两者都是二维状态，但矩阵连乘按区间长度递增、依赖同一区间内更短的子区间；本题按两个前缀下标递增、只依赖上方、左方、左上方相邻三格。看到 dp[i][j] 先确认两个下标各代表什么，再决定填表顺序。

按一次字符比较与一次列表读写为单位成本：二维表 $O(mn)$ 时间、$O(mn)$ 空间；滚动数组 $O(mn)$ 时间、$O(n)$ 空间；建表加回溯输出方案 $O(mn)$ 时间、$O(mn)$ 空间，回溯本身至多 $m+n$ 步。朴素枚举 text1 的所有子序列需要 $O(2^m\cdot n)$，在 $m=1000$ 时不可行。

三、从状态到答案：两题共同的三步

步骤	买包子	最长公共子序列
建表前判定	$\gcd>1$ 直接输出 INF，不填表	无前置分支，但要先确认求的是长度还是方案
状态值类型	布尔可达性	整数长度
依赖与顺序	容量外层、$x$ 内层递增，保证同容量可重复使用	$i$ 外层、$j$ 内层递增，保证三个相邻格已求出
答案加工	找连续 $m$ 个可达数确定停止位置，再统计窗口前的缺口	长度取 $dp[m][n]$；方案需从右下角反向追踪
范围保证	$L=\max(A_i)^2$，窗口之后无需再统计	第 0 行、第 0 列哨兵覆盖空前缀
压缩代价	固定上界简写版省去窗口扫描	滚动数组省空间，但失去回溯能力

两题的差别不在「会不会写 dp」，而在答案与状态之间还隔着几步：买包子隔着一次数论判定和一次全表统计，最长公共子序列在要求输出方案时隔着一次决策恢复。

方法比较

比较角度	买包子	最长公共子序列
题目所求	凑不出的正整数个数，可能为 INF	最长公共子序列的长度（或一种具体方案）
输入规模	$N\le100$、$A_i\le100$，枚举上界 $L=\max(A_i)^2$	$m,n\le1000$ 两个字符串
状态	$dp[x]$，布尔值，一维	$dp[i][j]$，整数长度，二维前缀
最后一步	再取一笼容量 $a$ 凑出 $x$	末字符相等则配对，否则跳过其中一侧末字符
依赖的更小状态	同一轮的 $dp[x-a]$	$dp[i-1][j]$、$dp[i][j-1]$、$dp[i-1][j-1]$
计算顺序	容量逐个加入，每种容量内 $x$ 递增	行 $i$ 递增，行内列 $j$ 递增
答案位置	不在表内：先找窗口，再统计窗口前的缺口	长度在 $dp[m][n]$；方案需回溯整张表
时间复杂度	$O(NL)$；INF 分支仅 $O(N\log M)$	$O(mn)$，滚动数组与回溯均不改变量级
辅助空间	$O(L)$	完整表 $O(mn)$；滚动数组 $O(n)$
空间优化代价	简写版省去窗口扫描，不改变渐近量级	压缩后无法恢复具体子序列

三点需要说清：

1. 两题的规模参数不同。买包子的 $L$ 由容量最大值决定，与 $N$ 无关；最长公共子序列的 $mn$ 由两个字符串长度决定。不能因为都出现「表」，就把复杂度一概写成平方级。
2. 空间优化减少的是「同时保存的信息量」，不是要计算的格子数。LCS 的滚动数组仍是 $O(mn)$ 时间；买包子的简写版把 $L$ 换成常数 10000，在题目约束下也只是换了常数值。
3. 答案类型必须在建表前确定。若题目要求输出一种最长公共子序列，仅保存 $dp[m][n]$ 的实现就不完整；若题目要求的是 INF，任何有限上界的统计都只是假答案。

从状态到答案的课堂检查顺序

先读清题目要的是值、计数还是方案，再判断是否存在无需建表的分支；接着用一句完整的话定义状态并写出边界与转移，确认依赖顺序和枚举范围都有保证；最后说明答案从哪里取、还需哪些加工，再按状态数与每格成本给出复杂度。写完 dp 数组不等于解完题，还要能回答「这张表说明了什么」。

课堂任务

任务一：先判 $\gcd$，再决定建不建表

对 [4,6]、[7]、[6,10,15]、[4,5,6] 分别给出 $\gcd$、是否需要进入动态规划以及最终答案。为什么不能用「两两互质」代替整体 $\gcd$ 判定？

参考答案

[4,6]：$g=2$，所有奇数凑不出，输出 INF，不建表。[7]：$g=7$，只有 7 的倍数可凑出，输出 INF，不建表。

[6,10,15]：两两 $\gcd$ 为 2、3、5，但三者整体 $g=1$，必须进入动态规划，答案为 15。若把判据写成「存在一对互质容量就认为有限」，这用例会被误判为 INF。

[4,5,6]：$g=1$，从 8 起所有整数可达，之前缺 $1,2,3,7$，答案为 4。

判定必须用全部容量的最大公约数：$g>1$ 时任何组合都是 $g$ 的倍数，非倍数有无穷多个；有限上界内统计出的个数只是截断结果，与题意无关。

任务二：检查内层循环方向

对容量 [4,5]，说明 $x=10$ 与 $x=14$ 为什么要求内层从小到大遍历。若改成从大到小，哪些数会被误判为凑不出？这时的模型变成了什么？

参考答案

加入容量 5 那一轮，$x=10$ 需要 dp[5]=1，而 dp[5] 是本轮由 $0+5$ 刚置真的；$x=14$ 需要 dp[9]=1，dp[9] 也是本轮由 $4+5$ 刚置真的。递增遍历让同一种容量可以被取用多次。

改成递减后，处理 $x=10$ 时 dp[5] 尚未更新，仍为假；$x=14$ 同理。这类需要重复取用同一容量的数都会被漏掉，答案因此被高估。此时每种容量最多取一次，模型退化成 01 背包，与「每种蒸笼无限笼」的题意不符。

任务三：连续窗口、统计范围与 10000

对 [4,5] 找出最早连续 $\min(A_i)$ 个可达整数，列出全部凑不出的正整数；说明为什么窗口之后不必再统计，以及 10000 到底是题目约束还是推导结果。

参考答案

$m=\min(4,5)=4$，最早连续 4 个可达数是 $12,13,14,15$，即 $t=12$。此后任意 $x\ge12$ 都可写成 $12,13,14,15$ 中的某一个反复加 4，因此全部可达。

检查 $1$ 到 $11$，凑不出的是 $1,2,3,6,7,11$，共 6 个；11 是其中最大者，6 才是答案。

官方约束是 $A_i\le100$。10000 来自上界 $L=\max(A_i)^2\le100^2$，是「在此约束下足够大」的枚举上界；脱离 $A_i\le100$ 就失去保证，例如 [9999,10000] 会令 $L$ 达到约 $10^8$，空间不再可行。窗口判定与固定上界是两件事：窗口说明「之后全部可达」，上界说明「窗口一定会在数组内出现」。

任务四：两个跳过方向与反向回溯

写出 text1 = "ab"、text2 = "cab" 的完整状态表，指出 $dp[2][2]$ 的两个候选值；若只保留其中一个方向会得到什么结果？再写出从 ("abcde","ace") 的 $(5,3)$ 出发的前两步回溯决策，并说明把「末字符不等」时状态置 0 求的是什么。

参考答案

状态表为第 0 行 [0,0,0,0]、第 1 行 [0,0,1,1]、第 2 行 [0,0,1,2]。$dp[2][2]$ 处 $b\ne a$，候选为 $dp[1][2]=1$ 与 $dp[2][1]=0$，正确答案是 $\max(1,0)=1$；只取 $dp[2][1]$ 会得到 0，后续格子随之出错，最终得不到正确答案 2（对应 "ab"）。

回溯前两步：$(5,3)$ 处 e == e，收录 e 并走到 $(4,2)$；$(4,2)$ 处 d != c，因 $dp[3][2]=2\ge dp[4][1]=1$，跳过 d 走到 $(3,2)$。继续会得到 c、a，逆序为 "ace"。

末字符不等时置 0 等于禁止跳过字符、要求公共部分连续，求的是最长公共子串，不再是子序列；本题只允许用两个跳过方向的较大值延续历史长度。

任务五：判断三种关于压缩与复杂度的说法

判断并修正：「用了两行滚动数组，LCS 的时间从 $O(mn)$ 降到 $O(n)$」「买包子只要把上界开得足够大，就能处理 INF 的情况」「两题都做了空间压缩，所以输出方案时也能沿用压缩后的实现」。

参考答案

三句都不成立。

滚动数组只减少同时保存的行数，$(m+1)(n+1)$ 个格子仍要逐个计算，时间仍是 $O(mn)$，降的是辅助空间 $O(mn)\to O(n)$。

$g>1$ 时凑不出的数有无穷多个，任何有限上界统计出的都只是上界以内的个数，与 INF 无关；必须先判定整体 $\gcd$ 并直接返回。上界负责保证「窗口一定出现在数组内」，不负责处理无穷分支。

压缩后历史决策已丢失。买包子压缩的是固定上界写法下的窗口扫描，最终答案本就是计数，不需要恢复方案；LCS 若要求输出一种具体子序列，必须保留 $O(mn)$ 的完整表或等价的决策记录，仅凭两行数组无法回溯。

课后实践： 用 Python 完成买包子的主实现与固定上界简写版，分别用 [1,5]、[7]、[4,4,5]、[6,10,15] 核对边界，并说明每组是否进入填表；再完成最长公共子序列的二维表、滚动数组与反向恢复三版，用 ("abc","def")、("ab","cab")、("abc","acb") 核对。每题都要写出「状态 → 答案」中间经过的判定与加工步骤。

相关导学：算法概览、动态规划的分类；区间 DP 迁移可继续做石子合并。