专题 17 动态规划入门 · 复习强化

考点：DP 的定义（A1）。

（A1）考点：DP 的定义——分解为重叠子问题，用状态记录答案按序推进。

解析：本题考查 DP 的定义。DP 的骨架：把原问题拆成一族小问题，每个小问题的答案存进 dp 数组的一格；算大问题时直接查表，不重算。与「一次扫描出答案」的贪心不同，DP 显式管理所有子问题。

排除法：A 选排序再扫描的人描述的是排序算法；C 选每次局部最优不反悔的人描述的是贪心；B 选全部列举逐个检查的人描述的是暴力枚举，DP 恰恰是为了避免重复枚举而生。

考点：状态与转移（A2）。

（A2）考点：状态与转移——状态是子问题的抽象（dp 数组一格），转移是子问题间的推导关系。

解析：本题考查状态与转移。状态回答「这格装的是哪个子问题的答案」，转移回答「这格怎么由更小的格算出来」。写 DP 前能用一句话说清状态含义，转移方程就有了着落。

排除法：C 选行号与输入输出切换的人把程序概念当成了算法概念；D 选数组大小与循环次数的人把工程参数当成了设计核心；B 选最终答案与打印语句的人完全没抓住「子问题」这层。

考点：初始化的意义（A3）。

（A3）考点：初始化的意义——给最小子问题直接赋答案，让转移有起点。

解析：本题考查初始化的意义。转移方程自底向上推导，最底层（如 $f[0]$、$f[1]$）无法再分解，必须人工给定；初始化就是这些「地基值」。地基错了，上面的楼层全部白搭（P3 展示后果）。

排除法：B 选清零当装饰的人不了解边界值直接参与转移；A 选代替转移方程的人把地基当成了整栋楼；C 选保证答案是零的人把手段误当成了结果。

考点：DP 与贪心（A4）。

（A4）考点：DP 与贪心——贪心局部选择不回头，DP 综合全部子问题保证全局最优。

解析：本题考查 DP 与贪心。贪心快而险：每步只看眼前，可能错过更优组合（01 背包就是反例，C7）；DP 慢而稳：枚举每个子问题的所有决策，答案有保证。两者复杂度常常一个是线性一个是多项式。

排除法：D 选贪心更慢的人把快慢关系弄反——贪心通常更快；A 选 DP 不能求最大值的人忘了背包、LIS 全是求最大值的 DP；B 选完全相同的人忽略了「是否考虑全部决策」这道分水岭。

考点：DP 与递推（A5）。

（A5）考点：DP 与递推——递推是填表机制，DP 是带着最优或计数目标的递推应用。

解析：本题考查 DP 与递推。$f[i]=f[i-1]+f[i-2]$ 是递推式；给它装上「爬楼梯方案数」的含义，它就成了 DP。可以说 DP 是递推的一种目标化使用：先设计状态含义，再找递推关系。

排除法：D 选毫无关系的人没看到公式形态完全一致；B 选方向固定的人把个别写法当成了本质，两者方向都随状态依赖而定；A 选只是改名的人忽略了 DP 的重心在「状态设计与最优性」，不只是套公式。

考点：DP 的四步（A6）。

（A6）考点：DP 的四步——定义状态、写转移方程、定初始化与边界、定计算顺序。

解析：本题考查 DP 的四步。顺序有讲究：先想清楚「一格装什么」，转移才有的放矢；初始化与边界和状态定义绑定；顺序保证被依赖的先算。本卷各代码题都是这四步的展开。

排除法：D 选写代码调试提交优化的人描述的是做题流程不是 DP 设计流程；C 选读题输出查格式的人连算法都没碰；B 选排序二分贪心输出的人把别的算法的口诀错安过来。

考点：最优子结构与无后效性（A7）。

（A7）考点：最优子结构与无后效性——大问题最优解含子问题最优解；状态之后的过程不受到达路径影响。

解析：本题考查最优子结构与无后效性。前者保证「合并子问题答案」合法，后者保证「同一状态殊途同归」——不管怎么到 $(i,j)$，之后的决策只看 $(i,j)$。两条都满足，dp 表才存得住通用答案。

排除法：B 选有序与互不相同的人把排序类前提错安过来；D 选数据范围限制的人把工程约束当数学性质；A 选必须求最大值的人忘了路径计数这类非最值 DP 同样适用。

考点：爬楼梯的 DP 视角（B1）。

（B1）考点：爬楼梯的 DP 视角——最后一步分类：$f[n]=f[n-1]+f[n-2]$。

解析：本题考查爬楼梯的 DP 视角。到达第 $n$ 阶的最后一步只有两种：从 $n-1$ 跨一阶、从 $n-2$ 跨两阶；两类互不重叠且穷尽所有可能，方案数相加。这是「按最后一步分类」的最经典入门转移，真题也考过它的费用版（I7、2024-J阅21）。

排除法：A 选乘 $2$ 的人没注意两类方案规模不同不可倍乘；B 选加 $1$ 的人把「新增一种」误当「新增一批」；D 选 $f[n]=n$ 的人给出的恰是另一问题的答案（错排步数之类），与方案数无关。

考点：最大子段和（B2）。

（B2）考点：最大子段和——f[i] 是以 i 结尾的最大子段和，答案扫全表取最大。

解析：本题考查最大子段和。状态定义带「以 i 结尾」是关键：它让 $f[i]$ 与 $f[i-1]$ 有了明确衔接关系（接上去或另起）；答案不在 $f[n]$ 而在全表最大值（G3）。这两点是子段类 DP 的通用设计。

排除法：B 选前 $i$ 个总和的人描述的是前缀和；D 选整段最大值的人丢掉了子段结构；C 选「前 i 个里任意子段最大」的人把状态含义说得过宽——那样转移写不出来。

考点：数字三角形的状态（B3）。

（B3）考点：数字三角形的状态——f[i][j] 是到该点（或从该点到底）的最优累计。

解析：本题考查数字三角形的状态。两个方向都行：自顶向下 $f[i][j]$ 是「走到这的最大和」，自底向上是「从这到底部的最大和」；后者边界简单（最后一行就是自己），是更常用的写法（M 组）。

排除法：B 选数字本身的人把输入当成了状态；A 选前 $i$ 行总和的人丢掉了路径结构；D 选路径条数的人把最值问题换成了计数问题，两者是不同的目标量。

考点：路径计数（B4）。

（B4）考点：路径计数——f[i][j] = f[i-1][j] + f[i][j-1]，方案数相加。

解析：本题考查路径计数。到 $(i,j)$ 的最后一步要么从上要么从左，两路方案互斥且穷尽，相加即得。计数 DP 与最值 DP 骨架相同，只是把 $\max$ 换成 $+$、把「选最大」换成「条条都算」。$3\times3$ 网格答案 $6=C(4,2)$（I4）。

排除法：C 选相乘的人没注意两条路不是独立组合而是并列来源；B 选取对角线的人把走法限制弄错（不允许斜走）；D 选 $m+n$ 的人给的公式与真实计数无关。

考点：不相邻取数（B5）。

（B5）考点：不相邻取数——f[i] 讨论第 i 个取或不取。

解析：本题考查不相邻取数。状态定为「前 $i$ 个数的最大和」，转移分两支：不取第 $i$ 个，答案承袭；取第 $i$ 个，则第 $i-1$ 个不能取，从更早的 $f[j]$（$j\le i-2$）衔接。I5 是它的完整代码。

排除法：A 选前 $i$ 个总和的人没考虑取或不取的抉择；C 选第 $i$ 个数本身的人状态退化成输入；D 选前 $i$ 个最大值的人丢掉了不相邻约束。

考点：台阶最小花费（B6）。

（B6）考点：台阶最小花费——f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])。

解析：本题考查台阶最小花费。爬楼梯方案数把 $+$ 换成 $\min$、再给每步贴上费用标签，就是本题：比较「从上一阶跨来」与「从上上阶跳来」谁更省。I7 实测 $\{10,15,20\}$ 起跳规则下答案 $25$；2024 年阅读真题正是这一模型。

排除法：B 选只一步步爬的人漏了跨两阶的分支；A 选只比较两级费用的人丢掉了历史累积；C 选两式相加的人把方案数转移错安到最值问题上。

考点：LIS 的定义（B7）。

（B7）考点：LIS 的定义——保持相对顺序、不要求连续的严格递增最长子序列。

解析：本题考查 LIS 的定义。三个要点：挑出的元素保持原相对顺序（可以跳着挑）、严格递增（$a_j<a_i$）、目标最长。与「最长连续上升段」的区别见 E5/P6——初学最易混。

排除法：C 选连续递增片段的人描述的是上升子段；D 选排序后长度的人丢掉了「子序列保持原序」的前提，排序会打乱次序；B 选最大最小差的人把序的结构简化成了两个数。

考点：一维滚动优化（B8）。

（B8）考点：一维滚动优化——只依赖近几项时用变量交替保存。

解析：本题考查一维滚动优化。$f[i]$ 只看 $f[i-1]$、$f[i-2]$，更早的值再也不会被引用；两个变量像接力棒一样滚动即可（I6 的 55）。省内存的本质是「历史无用」，不是玄学加速。

排除法：A 选更快得多的人把省内存错当提速——少掉的主要是空间；B 选数组溢出的人搞反了因果，滚动是主动选择不是被迫；D 选答案变大的人把存储优化与数值变化混为一谈。

考点：01 背包状态定义（C1）。

（C1）考点：01 背包状态定义——f[i][j] 是前 i 件、容量不超 j 的最大价值。

解析：本题考查 01 背包状态定义。「前 $i$ 件」+「容量 $j$」两个维度把「选了哪些」的全部关键信息压缩进下标；每件最多选一次是 01 的含义。滚动成一维后 $f[j]$ 隐含了「当前考虑过前若干件」。

排除法：C 选总重量的人丢掉了价值维度；D 选物品数的人丢掉了容量维度；B 选第 $i$ 件价值的人把状态退化成了输入。

考点：01 背包转移方程（C2）。

（C2）考点：01 背包转移方程——不选承袭 f[i-1][j]，选则腾容量加价值。

解析：本题考查 01 背包转移方程。每件物品只有两种决策：不选，答案与「前 $i-1$ 件、容量 $j$」相同；选，要先在容量里腾出 $w_i$（用 $f[i-1][j-w_i]$）再得 $v_i$。两者取 $\max$，决策完备。

排除法：A 选两项写反的人没逐项翻译 max 的两个参数；B 选两件不同物品的人下标里根本没有第二个物品的影子；C 选循环变量的人把语义参数当成了循环控制。

考点：容量循环必须倒序（C3）。

（C3）考点：容量循环必须倒序——倒序读旧值，正序同件反复计入。

解析：本题考查容量循环必须倒序。一维滚动时 $f[j]$ 与 $f[j-w_i]$ 同住一数组：倒序先算大容量，读 $f[j-w_i]$ 时它还是「没考虑第 $i$ 件」的旧值；正序先算小容量，同一件物品会被计入多次（K2 实测 $10$ 变 $12$），变成完全背包。

排除法：D 选更快的人把正确性需求错记成性能优化；B 选编译错误的人高估了编译器——运行正常但答案错；C 选自动扩容的人给循环方向安了不相干的职能。

考点：恰好装满的初始化（C4）。

（C4）考点：恰好装满的初始化——f[0]=0，其余负无穷标记不可达。

解析：本题考查恰好装满的初始化。只有空包（容量 $0$）天然可达且价值为 $0$；其余容量「还没装出来」要用负无穷表示不可达。转移照常取 $\max$，负无穷天然被合法值压制；终态若仍是负无穷即无解（K7）。

排除法：C 选全 $0$ 的人让「装不满」免费合法化，会报出错误价值（P3 实测）；D 选正无穷的人把方向完全弄反，max 会优先选无穷；A 选 $-1$ 的人看似标记，但 $-1$ 参与加法会污染数值（$-1+v_i$ 可能赢过合法值），必须用足够小的负数。

考点：不超过容量的初始化（C5）。

（C5）考点：不超过容量的初始化——全部为 0，空包即合法。

解析：本题考查不超过容量的初始化。「不超 $j$」的语义下，任何容量都允许「什么都不装」，价值 $0$ 是合法起点，全 $0$ 初始化正确。恰好装满与不超容量的差别全部落在初始化一行上，转移一模一样。

排除法：D 选负无穷初始化的人把恰好装满的规矩错搬过来——不超容量问题里空包处处合法、从价值 $0$ 起步；A 选正无穷的人方向就错，$max$ 会一路选中无穷；C 选随机初始化的人拿程序的确定性开玩笑——初值必须全部确定为 $0$ 才能保证答案确定。

考点：背包方案数转移（C6）。

（C6）考点：背包方案数转移——f[j] += f[j-w[i]]（倒序），f[0]=1。

解析：本题考查背包方案数转移。方案数 DP 把最值的 $\max$ 换成 $+$：到容量 $j$ 的方案 = 不选第 $i$ 件的旧方案 $f[j]$ + 选第 $i$ 件的方案 $f[j-w_i]$。$f[0]=1$ 表示「什么都不装」恰是一种方案。K4 实测 $\{1,2,3\}$ 装 $3$ 得 $2$。

排除法：A 选取 max 的人把计数问题当成了最值问题；B 选加一的人没注意新增的是「一整批」方案而非一个；D 选乘权重的人给方案数安了不相干的运算。

考点：01 背包与贪心（C7）。

（C7）考点：01 背包与贪心——不可分割使贪心失灵，DP 全决策枚举有保证。

解析：本题考查 01 背包与贪心。贪心按单位价值先装可能被「块头」卡住：大块占容量后，更划算的小件组合装不下。反例随手可造，DP 对每件「选/不选」全枚举，才保证最优。

排除法：C 选贪心永不对的人言过其实——部分背包（可分割）贪心恰恰正确；B 选单位价值溢出的人把数值细节当成了本质障碍；A 选代码长短的人把工程量当成了正确性依据。

考点：二维状态设计（D1）。

（D1）考点：二维状态设计——f[i][j] 是到格子 (i,j) 的目标量。

解析：本题考查二维状态设计。网格两个坐标天然对应两维下标，状态含义挂上目标量（最大和、最小费、路径数）即可。它与「前 $i$ 件容量 $j$」的背包一样，都是「两个自由度各占一维」的设计。

排除法：C 选原始数值的人把输入当状态；A 选矩形总和的人描述的是二维前缀和；D 选剩余容量的人把背包语境错搬到网格。

考点：矩阵最大路径和（D2）。

（D2）考点：矩阵最大路径和——f[i][j] = max(上, 左) + a[i][j]。

解析：本题考查矩阵最大路径和。只右/下走，$(i,j)$ 的最优必经上方或左方，取较优者加上本格值。L1 实测 {{1,2,3},{4,5,6},{7,8,9}} 得 $29$（贴着左边与底边走）。

排除法：B 选取 min 的人求成了最小路径；C 选对角线来源的人多加了斜走的非法路径；A 选 f[i-1][j-1] 的人跳过了中间必经的格子。

考点：二维转移来源（D3）。

（D3）考点：二维转移来源——只右/下走时来自上方与左方。

解析：本题考查二维转移来源。「反向看最后一步」：能走到 $(i,j)$ 的前一步只可能在 $(i-1,j)$（向下走）或 $(i,j-1)$（向右走）。来源集合由移动规则决定，规则变（可斜走）来源就变。

排除法：B 选下方右方的人把方向整个弄反，那是「从终点往回走」的视角却还按正向依赖写；A 选四周相邻的人没注意不允许向上、向左；D 选仅对角线的人又虚构了斜走。

考点：边界行与列（D4）。

（D4）考点：边界行与列——首行首列单来源，需单独初始化。

解析：本题考查边界行与列。首行每格只能从左邻到达，首列只能从上邻到达，双来源转移在边界上会引用不存在的格；干脆按单来源规则直接累加初始化（L2 的 1 3 6）。

排除法：D 选数据最大的人把边界与数值扯在一起；B 选编译错误的人高估了检查，越界读的是垃圾值照样运行；C 选必须置零的人把「初始化」简单化成了清零，首行首列恰恰要累加。

考点：障碍物的处理（D5）。

（D5）考点：障碍物的处理——障碍格 f 置 0，其余照常累加。

解析：本题考查障碍物的处理。路径数为 $0$ 表示「没有任何路径经过此格」，自动阻断后续格从它取数；转移公式完全不用改，只在循环里加一个障碍判断。L3 实测中心障碍后 $f[2][2]=2$。

排除法：A 选跳过不循环的人漏掉的格子还有后续格子依赖它，跳过会读到未初始化值；B 选正无穷的人在计数问题里显然荒谬；D 选平均值的人给计数安了不存在的运算。

考点：二维 DP 的复杂度（D6）。

（D6）考点：二维 DP 的复杂度——状态数 mn 乘单格转移 O(1)。

解析：本题考查二维 DP 的复杂度。$m\times n$ 个状态每格只比两个来源，总时间 $O(mn)$、空间同为 $O(mn)$（可滚动到 $O(n)$）。复杂度口诀「状态数 × 单状态转移代价」在一切 DP 上通用。

排除法：D 选 $O(m+n)$ 的人只数了边界长度；A 选带对数的人给单格转移虚加了排序代价；B 选 $O(1)$ 的人忘了表本身要逐格填。

考点：二维滚动优化（D7）。

（D7）考点：二维滚动优化——逐行算，上一行用完即弃。

解析：本题考查二维滚动优化。$f[i][*]$ 只依赖 $f[i-1][*]$ 与本行左侧，算完一行后上上行彻底无用，一维数组滚动保存最近一行即可（L4 展开「旧 $f[j]$ 恰是上一行」的对位关系）。空间从 $O(mn)$ 降到 $O(n)$。

排除法：D 选必然更快的人又把省空间当提速；A 选必须压缩的人把优化选项说成了强制；C 选能算更大答案的人把内存与数值范围混为一谈。

考点：LIS 的严格性（E1）。

（E1）考点：LIS 的严格性——允许相等即最长不下降子序列。

解析：本题考查 LIS 的严格性。判断条件 $a_j<a_i$（严格）与 $a_j\le a_i$（不下降）一词之差决定相等元素能否并列入选；J3 实测 $\{1,3,2,2,4\}$ 不下降得 $4$（1 2 2 4）。读题认清「上升/不下降」是第一步。

排除法：A 选最长下降的人把不等号方向改了而不是放宽；B 选无区别的人没算过 $\{2,2,2\}$ 这类数据——严格 LIS 为 $1$、不下降为 $3$；C 选公共子序列的人跳到了另一个双序列问题。

考点：LIS 的转移方程（E2）。

（E2）考点：LIS 的转移方程——f[i] 是以 a[i] 结尾的 LIS 长度。

解析：本题考查 LIS 的转移方程。「以 $i$ 结尾」让 $f[i]$ 与所有 $j<i$ 有了明确的衔接条件（$a_j<a_i$ 时接上）；初值 $f[i]=1$（自己单选）。与最大子段和同属「结尾型」设计。

排除法：A 选「前 i 个的 LIS」的人写不出转移——不知道结尾是谁就没法接龙；D 选上升对数的人把计数目标错当长度；B 选排名的人把序结构错当 DP 值。

考点：LIS 的答案位置（E3）。

（E3）考点：LIS 的答案位置——扫全部 f[i] 取最大，结尾任意。

解析：本题考查 LIS 的答案位置。「以 i 结尾」的定义不保证最长链恰在末项结束（结尾可能在任何位置），答案取 $\max f[i]$。对比「前 i 个」型定义答案在 $f[n]$——状态定义决定取答案的位置（G3）。

排除法：A 选 $f[n]$ 的人给 $\{9,1,2\}$ 这类数据立刻翻车（最长链 $1,2$ 结尾在下标 $2$，$f[3]$ 只是 $1$）；C 选 $f[1]$ 的人假设最长链必含首项，不成立；D 选平均值的人把离散结构当成了统计量。

考点：LIS 的序列还原（E4）。

（E4）考点：LIS 的序列还原——转移时记 pre[i]，从结尾回溯。

解析：本题考查 LIS 的序列还原。$pre[i]$ 记录 $f[i]$ 的最优来源 $j$；找到答案结尾后沿 $pre$ 一路走回开头，倒序输出即还原序列。J5 实测 $\{2,5,3,7\}$ 还原 2 5 7。「带 pre 回溯」适用于一切要输出方案的 DP。

排除法：B 选直接输出 f 的人输出的是长度表不是序列；A 选无法还原的人低估了记录来源的威力；D 选排序输出的人把原序丢掉，子序列定义就不成立了。

考点：子序列与子段（E5）。

（E5）考点：子序列与子段——子序列可不连续，子段必须连续。

解析：本题考查子序列与子段。LIS、LCS 是子序列问题（跳着挑），最大子段和是子段问题（连续一段）；两者转移结构不同——子段型与相邻格衔接，子序列型可从任意更早的格衔接。混用概念是 P6 的错误根源。

排除法：A 选两者相同的人没做过 $\{1,9,2,10\}$：LIS 为 $3$ 而最长上升子段只有 $2$；C 选定义互换的人正好弄反；B 选只能取一半的人给子序列加了不存在的限制。

考点：LIS 的多条方案（E6）。

（E6）考点：LIS 的多条方案——同长时方案相加，更长时覆盖重置。

解析：本题考查 LIS 的多条方案。$f[j]+1=f[i]$ 说明又发现一条等长来源，$cnt[i] += cnt[j]$；$f[j]+1>f[i]$ 说明更长链出现，覆盖 $f$ 并重置 $cnt[i]=cnt[j]$。O3 实测 $\{1,3,2\}$ 得长度 $2$ 方案 $2$。

排除法：C 选直接覆盖的人丢掉了等长的其他来源；A 选取最大的人把计数当最值；B 选清零的人在恰好该累加的时候清了账。

考点：DP 与分治（F1）。

（F1）考点：DP 与分治——分治子问题独立，DP 子问题重叠需记录。

解析：本题考查 DP 与分治。归并排序左右两半互不相干（独立），算完即弃；DP 的子问题被反复用到（如斐波那契的 $f[5]$ 会被多条路径依赖），不记录就重复计算、指数爆炸。重叠与独立是两种划分方式的分水岭。

排除法：C 选只能分两半的人把常见形态当成了定义，DP 状态可有任意依赖；B 选 DP 不能递归的人忘了记忆化搜索就是递归 DP；D 选分治不做最优问题的人没见过归并求逆序对等应用。

考点：DP 与回溯（F2）。

（F2）考点：DP 与回溯——回溯全枚举指数级，DP 记录共享多项式。

解析：本题考查 DP 与回溯。全排列式回溯把每条路走到黑，路径数指数增长；DP 发现「走到同一状态之后的答案相同」，算一次存表共享。「记录换枚举」是 DP 的灵魂，也是它能多项式求解的原因。

排除法：D 选回溯总是更快的人把指数级当成了快；A 选循环写法代价相同的人没理解共享子问题带来的量级差异；C 选都不能计数的人忘了路径计数 DP 恰是计数利器。

考点：DP 的复杂度估算（F3）。

（F3）考点：DP 的复杂度估算——状态总数乘单状态转移代价。

解析：本题考查 DP 的复杂度估算。LIS：$n$ 个状态、每状态内层 $O(n)$，总 $O(n^2)$；01 背包：$nC$ 状态、$O(1)$ 转移，总 $O(nC)$。先数状态维度的乘积，再看每个状态要比较多少来源。

排除法：A 选数组大小的人只看了空间没看每格工作量；C 选输入位数的人把位运算的度量错安过来；D 选答案大小的人把输出量当成了计算量。

考点：最优子结构反例（F4）。

（F4）考点：最优子结构反例——最长简单路径的局部最优拼不出全局最优。

解析：本题考查最优子结构反例。图上「$u$ 到 $v$ 的最长路」若取「$u$ 到中途点的最长」再拼尾巴，尾巴可能途经前段用过的点，简单路径条件被破坏——子问题最优不能保证组合合法。所以它不能直接 DP（问题在提高级另有解法，初赛知道反例即可）。

排除法：B 选数组存不下的人把工程限制当数学障碍；A 选必须连通的人没抓住要害，连通图照样反例；D 选「无最优子结构的问题不存在」的人把教科书级反例（最长简单路径）当成了不存在。

考点：DP 的常见错误（F5）。

（F5）考点：DP 的常见错误——状态模糊、转移漏决策、边界不当。

解析：本题考查 DP 的常见错误。三大高发区：状态说不清（一句定义都写不出）、转移漏分支（如背包漏「不选」、H3）、初始化错位（恰好装满错用全零、P3）。改错先按 A6 四步自查，再用 G6 打表定位。

排除法：B 选语法类错误（分号头文件）的人描述的是编程入门坑不是 DP 特有坑；C 选命名注释的人把代码风格当成了算法错误；D 选输入输出样例的人把环境问题当成了设计问题。

考点：状态设计三问（G1）。

（G1）考点：状态设计三问——这格是哪个子问题、怎么推出来、地基是什么。

解析：本题考查状态设计三问。三问分别对应状态定义、转移方程、初始化——A6 四步的前三步浓缩成可自问的口诀。设计卡壳时按三问顺序过一遍，通常卡在第一问。

排除法：A 选数组大小循环层数的人谈的是实现细节不是设计；B 选数据组数样例时限的人谈的是比赛环境；D 选排序去重递归循环的人谈的是别的算法的工具箱。

考点：转移顺序（G2）。

（G2）考点：转移顺序——被依赖的先算。

解析：本题考查转移顺序。$f[i]$ 依赖更小下标就从小到大；数字三角形自底向上时依赖更大行号，就从最后一行往上。顺序由依赖方向决定，不是死记「从小到大」——倒序依赖倒着算（背包的容量维同理）。

排除法：D 选一律从小到大双层循环的人在三角形、背包的容量维上立刻翻车；B 选顺序无所谓的人没遇到过读未初始化格的教训；A 选从答案倒算一遍的人把「输出路径回溯」错当成了「计算顺序」。

考点：答案的位置（G3）。

（G3）考点：答案的位置——结尾型扫全表，前缀型取 f[n]。

解析：本题考查答案的位置。「以 $i$ 结尾」型（最大子段和、LIS）答案取 $\max_i f[i]$；「前 $i$ 个」型（爬楼梯、背包）答案看 $f[n]$ 或 $f[C]$。取答案的位置由状态定义决定，写完代码先核对这一处。

排除法：C 选永远在 $f[n]$ 的人会被 LIS 打脸（H4）；A 选永远在 $f[0]$ 的人方向整个反了；B 选最后被赋值处的人把程序行为当成了设计依据。

考点：DP 数组的大小（G4）。

（G4）考点：DP 数组的大小——按状态定义开并给边界留位。

解析：本题考查 DP 数组的大小。$f[i]$ 从 $0$ 起时开 $n+1$；背包按容量开 $C+1$。多留一两格放 $f[0]$ 这类边界比压着开更安全——越界是阴沟里翻船（P5）。

排除法：C 选越大越好的人内存会被大样例教做人；D 选固定开 $100$ 的人在千级数据上立刻爆；B 选等于答案值的人把两个不相干的量绑在了一起。

考点：下标边界处理（G5）。

（G5）考点：下标边界处理——循环条件拦住负下标与超界。

解析：本题考查下标边界处理。$j-w_i\ge 0$、$i-1\ge 0$ 这类约束写进循环边界（背包 j >= w[i]）或条件表达式（网格的三目判断），保证每次访存合法。边界处理与 G4 的数组大小配合，构成 DP 代码的安全网。

排除法：C 选越界无所谓的人把未定义行为当成了运气；A 选全部加一的人平移下标、避开下标 $0$ 的特判，能躲一部分问题但边界判断仍少不了；D 选开小数组防越界的人把防护做成了自杀。

考点：打印 DP 表调试（G6）。

（G6）考点：打印 DP 表调试——与手算小样例逐格核对。

解析：本题考查打印 DP 表调试。小规模样例先手算整张表，程序打印后逐格比对，第一个不一致的格就是错误转移的现场——比盯着代码空想快一个数量级。M2 的 DP 表输出就是这种调试的直接产物。

排除法：C 选盯代码的人效率最低且最容易漏；B 选提交碰运气的人在考场上没有运气可碰；A 选换 long long 的人把类型问题当成了万能药。

考点：背包正序的错误（H1）。

（H1）考点：背包正序的错误——同一物品反复计入，变成完全背包。

解析：本题考查背包正序的错误。正序时小容量先更新，同一轮里 $f[j-w_i]$ 已经计入过第 $i$ 件，$f[j]$ 再引用它就把这件数了第二遍。K2 用真题级数据实测倒序 $10$、正序 $12$；「正序=完全背包」这一巧合正是 C3 的原理复用。

排除法：A 选程序崩溃的人高估了故障形态——它安静地给错答案；C 选只算第一件的人没追踪后续轮次，全部物品都在被重复选；B 选输出恒为 $0$ 的人没看到转移确实在更新数值。

考点：初始化错误（H2）。

（H2）考点：初始化错误——恰好装满错用全零，装不满被合法化。

解析：本题考查初始化错误。全零初始化下每个容量都「免费可达」，装不满的状态带着 $0$ 价值参与 max，可能压过真实可达的小价值方案。P3 实测一件 $w=2$、$C=4$：正确模型应报不可达，错初始化报 $5$。

排除法：A 选编译错误的人又把逻辑错当语法错；B 选死循环的人把初始化与循环条件混为一谈；D 选没有影响的人没算过恰好装满与不超容量两版答案的差别。

考点：转移漏选（H3）。

（H3）考点：转移漏选——漏「不选」分支即被迫全选。

解析：本题考查转移漏选。背包每件有两个决策，max 里两项各管一个；漏掉「不选」（$f[i-1][j]$）一项，等于强制每件必选——总重随时可能爆容量，答案自然错。转移必须覆盖决策全集。

排除法：C 选等价原方程的人没注意少了一个 max 分支；D 选只影响速度的人没发现答案都变了；B 选数组溢出的人把语义错误错报成内存错误。

考点：LIS 答案取错（H4）。

（H4）考点：LIS 答案取错——f[n] 不是答案，结尾型要扫全表。

解析：本题考查 LIS 答案取错。$\{9,1,2\}$ 的最长链是 $1,2$，结尾在下标 $2$，而 $f[3]$（以 $9$ 结尾）只是 $1$——取 $f[n]$ 直接错。正确做法取 $\max f[i]$。状态定义（E2）与取答案位置（G3）要配套检查。

排除法：C 选「$f[n]$ 一定是 $0$」的人换了个错法，$f[n]$ 有值但未必最大；B 选「数组乱序」的人把实现细节当成了设计缺陷；D 选「只能从第一项开头」的人给 LIS 加了不存在的限制。

考点：DP 综合判断（H5）。

（H5）考点：DP 综合判断——每子问题只算一次，记录换时间。

解析：本题考查 DP 综合判断。DP 表保证每个子问题恰好计算一次，重叠子问题由「查表」代替「重算」——这是它对比暴力枚举的本质优势。其余选项的错误各自对应一条常见误解。

排除法：D 选必须递归的人忘了迭代填表同样正统；A 选任何问题都有多项式 DP 的人高估了它的疆域——TSP 之类至今没有多项式解法；B 选转移与循环顺序无关的人没读过 G2。

考点：爬楼梯方案数（I1）。

（I1）考点：爬楼梯方案数——f[1]=1、f[2]=2 起步填到 f[5]=8。

解析：本题考查爬楼梯方案数。$f[3]=3$、$f[4]=5$、$f[5]=8$——斐波那契数列换了身衣服。方案数转移「末步分类相加」，从两个地基值一路推到目标。

排除法：C 答 $5$ 的人停在 $f[4]$；D 答 $13$ 的人多推一步到了 $f[6]$；B 答 $7$ 的人中途加错一次。

考点：最大子段和输出（I2）。

（I2）考点：最大子段和输出——{-2,3,-1,2,-5} 的答案是 4。

解析：本题考查最大子段和输出。逐格算：$f=-2,3,2,4,-1$，最大 $4$（子段 $3,-1,2$）。注意负前缀被 $\max(\cdot, a_i]$ 及时丢弃，这是「另起炉灶」分支的功劳。

排除法：A 答 $-2$ 的人只算了首格；D 答 $5$ 的人把 $3+2$ 当成了连续子段，中间隔着 $-1$；B 答 $3$ 的人漏了 $-1$ 后还能接 $2$。

考点：数字三角形最大路径（I3）。

（I3）考点：数字三角形最大路径——经典 7/3 8/8 1 0/2 7 4 4 三角形答案 25。

解析：本题考查数字三角形最大路径。自底向上逐行取大：底层照抄；第三层 $8{+}7{=}15$、$1{+}7{=}8$、$0{+}4{=}4$；第二层 $3{+}15{=}18$、$8{+}8{=}16$；顶层 $7{+}18{=}25$。路径为 $7,3,8,7$。

排除法：C 答 $30$ 的人把更大的三角形经典数据记串了；B 答 $22$ 的人某层取小时算错；A 答 $7$ 的人只输出顶层数字。

考点：网格路径计数（I4）。

（I4）考点：网格路径计数——3x3 网格右下角路径数 6。

解析：本题考查网格路径计数。表逐格填：$1,1,1 / 1,2,3 / 1,3,6$，右下角 $6$——恰是 $C(4,2)$（四步中选两步向下）。计数转移把每格两路来源相加。

排除法：D 答 $9$ 的人以为等于格子数；B 答 $3$ 的人只数了单调走法的一半；C 答 $12$ 的人把来源相加了两次。

考点：不相邻取数（I5）。

（I5）考点：不相邻取数——{3,1,4,1,5} 不相邻最大和 12。

解析：本题考查不相邻取数。最优取 $3,4,5$（下标 $0,2,4$ 两两隔开）和为 $12$。逐格算 $f=3,1,7,4,12$（$f[4]$ 从 $f[2]{+}5=12$ 取到最大）。约束「隔至少一个」在转移上表现为只能衔接 $j\le i-2$ 的来源。

排除法：A 答 $14$ 的人把 $3{+}1{+}4{+}...$ 之类的相邻项也算进去；B 答 $9$ 的人取的 $3,4$? 或 $4,5$ 少拿了一个可取的；C 答 $5$ 的人只取了单个最大值。

考点：斐波那契滚动（I6）。

（I6）考点：斐波那契滚动——两变量滚到第 10 项 55。

解析：本题考查斐波那契滚动。$1,1$ 起步：$2,3,5,8,13,21,34,55$——第 $10$ 项 $55$。变量 $a,b$ 像接力棒轮转，历史值自然丢弃，是 B8 滚动思想的四行实现。

排除法：A 答 $34$ 的人少滚一轮；C 答 $89$ 的人多滚一轮；D 答 $10$ 的人把项数当成了值。

考点：台阶最小花费（I7）。

（I7）考点：台阶最小花费——{10,15,20} 从 0 或 1 起跳、跳离付费模型下 f[3]=25。

解析：本题考查台阶最小花费。$f[1]=10$（从 $0$ 起跳付 $10$）；$f[2]=\min(f[1]{+}15,\ f[0]{+}10)=10$（走 $0\to2$）；$f[3]=\min(f[2]{+}20,\ f[1]{+}15)=25$（走 $0\to1\to3$ 付 $10{+}15$）。模型关键：付费发生在「跳离」时。2024 年阅读真题即此模型。

排除法：A 答 $15$ 的人只算了起跳费用没算两跳；C 答 $30$ 的人走了 $0\to2\to3$ 全程付 $10{+}20$，比 $25$ 贵；D 答 $45$ 的人把三段费用全加。

考点：LIS 的长度（J1）。

（J1）考点：LIS 的长度——{3,1,4,1,5,9,2,6} 的 LIS 为 4。

解析：本题考查 LIS 的长度。最长链如 $3,4,5,9$ 或 $1,4,5,9$，长度 $4$。双循环 $O(n^2)$ 逐格比较前驱取最大；答案扫全表。

排除法：B 答 $8$ 的人以为整个序列都递增，两个 $1$ 已破坏严格性；D 答 $5$ 的人把不合法的链（含相等或降序对）也数了进去；C 答 $3$ 的人漏了更长的链。

考点：f 数组的值（J2）。

（J2）考点：f 数组的值——{1,3,2,4} 的 f 为 1 2 2 3。

解析：本题考查 f 数组的值。逐格算：$f[0]=1$（$1$ 单选）；$f[1]=2$（$1,3$）；$f[2]=2$（$1,2$，接 $f[0]$）；$f[3]=3$（$1,3,4$ 或 $1,2,4$）。输出 1 2 2 3——f 表本身就是理解 LIS 转移的最佳教具。

排除法：B 答 1 1 2 2 的人对 $f[1]$ 接错来源；C 答 1 2 3 4 的人以为 f 记录的是元素值或位置；A 答 1 2 2 4 的人末格把元素值 $4$ 当成了长度。

考点：最长不下降（J3）。

（J3）考点：最长不下降——{1,3,2,2,4} 用 <= 得 4。

解析：本题考查最长不下降。条件放宽为 $a_j\le a_i$ 后，两个 $2$ 可并列入选：链 $1,2,2,4$ 长度 $4$。与严格版差在一个等号，读题审「上升/不下降」就是审这个等号。

排除法：C 答 $3$ 的人还在用严格版口径；B 答 $5$ 的人以为全序列都合法，$3$ 到 $2$ 是下降；D 答 $2$ 的人低估了链长。

考点：最长下降（J4）。

（J4）考点：最长下降——{5,3,4,2,1} 把小于换成大于得 4。

解析：本题考查最长下降。条件 $a_j>a_i$ 让链往低处走：$5,3,2,1$ 或 $5,4,2,1$，长度 $4$。LIS 家族（上升/不上升/下降/不下降）全靠不等号方向与开闭调节。