CSP-J 学习卷 L28 · 动态规划入门

规则：动态规划 = 把问题拆成重叠的子问题，用状态数组存答案，用转移方程递推，用「存」换「重复算」。

考点：动态规划基本思想的识别。

解析：DP 的核心动作有三个：定义状态（dp[i] 表示什么）、写转移方程（从更小的子问题推当前的）、定边界初值。它和「拆成独立小问题」的分治、「每步选局部最优」的贪心、「全枚举」的暴力是四条不同的路。

排除法：「相互独立的小问题」是分治的特征（归并排序），DP 的子问题恰恰大量重叠；「每步选最优」是贪心；「枚举所有方案」是暴力，DP 正是为了不枚举而生的。

规则：贪心解决的是「最优解」问题（最短路、最少步数）；走楼梯问的是「方案数」，是计数问题，贪心只能输出一种方案，天然数不出总量。

考点：DP 与贪心的适用范围分野。

解析：$n = 4$ 时走法有 5 种（1111、112、121、211、22）。贪心「尽量走 2 级」只会给出「22」这一种，答非所问。想数全走法，必须按「最后一步跨 1 级还是 2 级」分类递归，这正是 DP 的雏形。

排除法：「越界」与贪心无关，走法数是逻辑问题；「变 $2^n$」没有任何依据；「死循环」更无从谈起。

规则：重叠子问题 = 同一个子问题被多个「父问题」需要，递归树里出现多次。

考点：重叠子问题的判断。

解析：$f(5)$ 的递归树里，$f(3)$ 既被 $f(4)$（因为 $f(4)=f(3)+f(2)$）需要，也被 $f(5)$（$f(5)=f(4)+f(3)$）需要，出现两次；$f(2)$、$f(1)$ 出现得更多。这种「重复计算」正是 DP 要消除的对象。

排除法：累加和每个子问题只被用一次；归并排序两半互不相干；二分查找每次只进一半、状态不重复。

规则：朴素递归的时间复杂度是 $O(2^n)$（每个子问题被重复求解），递推是 $O(n)$（每个状态只算一次）。

考点：重叠子问题导致的重复计算。

解析：$f(40)$ 的递归树里 $f(39)$、$f(38)$……每个子问题都被反复求，调用总次数超过 $10^9$ 量级；而递推循环从 $g[0]$ 一路推到 $g[40]$，每次计算都是 $O(1)$ 的加法，总共 40 次。同一数学定义，两种实现差了天文数字——这正是「把答案存下来」的价值。

排除法：压栈开销只是常数差距，改变不了量级；溢出不会变慢只会错值；递归版没有任何输出。

规则：$f(6)$ 朴素递归共调用 $f$ 函数 $25$ 次（$f(6)=8$ 的输出另说，cnt 记的是调用次数）。

考点：朴素递归调用次数的追踪（递归树）。

解析：记 $T(n)$ 为调用次数，$T(0)=T(1)=1$，$T(n)=T(n-1)+T(n-2)+1$。逐层算：$T(2)=3$、$T(3)=5$、$T(4)=9$、$T(5)=15$、$T(6)=25$。程序先输出 f(6) = 8，再输出 cnt = 25。

排除法：$13$ 是 $f(7)$ 的值不是调用次数；$15$ 是 $T(5)$；$12$ 没有依据。

规则：最优子结构 = 大问题的最优解包含（能由）子问题的最优解（构造）。

考点：最优子结构的定义。

解析：打家劫舍里，「前 $i$ 家的最大金额」要么等于「前 $i-1$ 家的最大金额」，要么等于「前 $i-2$ 家的最大金额加第 $i$ 家的钱」——不管哪条，都只用到了更小规模的「最优解」。「算过一次不变」是状态记录的特性；「只能一个解」是误解；「中间位置」是无稽之谈。

排除法：「算过不变」说的是记忆化/递推的表，不是最优子结构本身；「只能一个解」与最优子结构无关，子问题可以有多个并列最优；「中间位置」是典型胡思乱想。

规则：无后效性 = 未来的决策只依赖当前状态的值，不依赖「这个值是怎么来的」；状态本身已经包含了做决策所需的全部信息。

考点：无后效性的定义与含义。

解析：爬楼梯算 dp[5] 只需要 dp[4] 和 dp[3]，不需要知道 dp[4] 具体是「先 2 级再 2 级」还是「先 1 级再 1 级再 2 级」——那些历史细节不影响 dp[5]。一旦某个问题的最优决策必须知道历史路径，简单一维 DP 就会失效（这是许多进阶问题的难点来源）。

排除法：「不会更新」误解了状态的含义（dp 数组在递推过程中本来就被逐格填值）；「每格只能用一次」没有这回事；「非负整数」与无后效性毫无关系。

规则：DP 成立的两个前提是「最优子结构」和「无后效性」；当未来决策依赖历史路径时，无后效性被破坏，状态里必须加入路径信息（通常导致状态维度爆炸）。

考点：无后效性被破坏时 DP 失效。

解析：标准的 DP 状态要求「dp[i] 的值一旦确定，就能作为独立信息参与更大家伙的决策」。若最优决策还依赖于「之前怎么选的」，那么同样停在 $i$ 的两种走法对未来的影响不同，一个 dp[i] 装不下两种未来——强行用一个数递推，结果必然失真。

排除法：「数组太小」不是本质原因，本质是信息不够；「字符串」无关；「超时」和正确性无关。

规则：分治的子问题「互不相交」，做完合并即可；DP 的子问题「互相重叠」，所以要存答案避免重算。

考点：DP 与分治的区分。

解析：归并排序把数组对半切开，左半、右半互不相干，各自排好后合并；斐波那契的两个递归分支共享了大量子问题。分治里「存答案」没有意义（每个子问题只用一次），DP 里「存答案」是关键（同一子问题反复被用）。子问题是否重叠是两者最简单的判别器。

排除法：DP 也能写递归（记忆化），分治也能用循环模拟；速度由算法本身决定与类别无关；DP 也处理最小化、计数、可行性问题。

规则：DP 总时间 $\approx$ 状态数 $\times$ 每状态转移数，即 $O(S \times M)$。

考点：DP 复杂度的通用口径。

解析：每个状态都要枚举一遍它的转移并取最优，所以总工作量 = 状态数乘每状态的转移数。爬楼梯 $S = n$、$M = 2$，总 $O(2n) = O(n)$；0/1 背包 $S = nV$、$M = 2$，总 $O(nV)$；LIS $S = n$、$M = n$，总 $O(n^2)$。

排除法：$O(S+M)$ 漏掉了「每个状态都做 M 次」；$O(S^2)$ 是把 M 强行当 S；$O(2^S)$ 是搜索的复杂度。

规则：状态数 $(n+1)(V+1) \approx nV$，每状态 2 种转移，总 $O(nV)$。

考点：用「状态数 $\times$ 转移数」估复杂度。

解析：状态是「前几件 + 容量多少」，共 $n \times V$ 个；每个状态只做一次 max 二选一，常数时间。所以总 $O(nV)$。$n = 1000$、$V = 1000$ 时约 $10^6$ 次操作，轻松可过；如果写成枚举选哪些物品，就是 $O(2^n)$ 了。

排除法：$O(n^2)$ 把 $V$ 误当成 $n$；$O(V^2)$ 漏了 $n$ 维；$O(2^n)$ 是暴力子集枚举的复杂度。

规则：DP 需要最优子结构与无后效性；重叠子问题决定「是否值得用 DP」（有重叠才赚）；「数据是正整数」纯属虚构。

考点：DP 适用条件的辨析。

解析：最优子结构和无后效性是 DP 正确性的硬前提；重叠子问题是 DP 能提速的软前提（没有重叠也能 DP，只是和递归一样慢）；数据正负与 DP 无关，打家劫舍照样处理负收益。

排除法：「最优子结构」「无后效性」是必需；「重叠子问题」虽然不决定正确性，但它正是 DP 区别于分治的价值所在，通常也算前提——严格讲本题问的是「不是必需」，唯一确定错误的是「正整数」。

规则：贪心适合「每步的局部最优能推出全局最优」的问题；DP 适合「解由若干子问题的最优组合而成」的问题，它用状态 + 转移覆盖所有可能。

考点：贪心与 DP 的选型判断。

解析：走楼梯的每种走法互不覆盖，贪心选一种就丢掉了其他；打家劫舍「偷第 $i$ 家」与「不偷」是互斥选项，必须比较两条子问题路径。这类「每条路都要考虑」的问题正是 DP 的主场：状态存每个子问题的最优，转移枚举分支，从底到顶拼出全局最优。

排除法：「代码短」不是选型理由；「整数/实数」与算法类别无关；「不用定义状态」恰恰相反，状态定义是 DP 第一步。

规则：状态是「到达第几级」，从 0 到 n 共 $n+1$ 个；数组大小就是状态数，开 n+1。

考点：状态数组大小的确定。

解析：dp[0] 表示站在地面，dp[n] 表示到第 n 级，都是合法状态，所以数组长度至少 $n+1$。竞赛里常开大一点（如 $n+10$）防边界手滑，但原理上状态数决定数组大小。

排除法：开到 $n$ 会越界访问 dp[n]；$2n$ 没有必要；「随便开」违背了状态数 = 数组大小的基本对应。

规则：状态定义回答「dp[i] 存什么」——这里存「到第 $i$ 级的走法数」。

考点：一维 DP 的状态定义。

解析：题目要的是「走法数量」，所以 dp[i] 存的是数量。「最少步数」是另一类问题（贪心/最短路）的答案口径，走法数不需要最少。状态定义一旦定错，后面转移方程、初值全都会跟着错。

排除法：「最少步数」答非所问；「总长度」「高度」是物理量，与走法数无关。

规则：转移方程 = $dp[i] = dp[i-1] + dp[i-2]$（斐波那契式递推）。

考点：一维 DP 转移方程的写法。

解析：到第 $i$ 级的走法分成两类：最后一步跨 1 级（来自第 $i-1$ 级）或跨 2 级（来自第 $i-2$ 级），两类相加即可，因为「到第 $i-1$ 级的每种走法后面接 1 级」和「到第 $i-2$ 级的每种走法后面接 2 级」互不重复。

排除法：+1 是「最后一步只有一种」的错误理解；\times 2 是「每一步两种选择」的错误叠乘；max 是求最优不是数方案。

规则：dp[1] = 2 使整个递推链偏大：$dp[2]=2+1=3$、$dp[3]=3+2=5$，比正确值 3 大 2。

考点：边界初值错导致全盘错。

解析：正确的 1/2 阶爬楼梯 $dp[3]=dp[2]+dp[1]=2+1=3$（走法：111、12、21 三种）。误把 dp[1] 写成 2 后，$dp[2]=2+1=3$（正确应为 2）、$dp[3]=3+2=5$。初值错一格，误差沿着递推向下游传播。

排除法：$3$ 是正确版本；$4$ 是只错一处的中间值；$6$ 是把 $dp[0]$ 也写错的更大偏差。

规则：$dp$ 就是斐波那契数列：$dp[2]=2$、$dp[3]=3$、$dp[4]=5$、$dp[5]=8$、$dp[6]=13$、$dp[7]=21$。

考点：爬楼梯递推的数值追踪。

解析：$dp[2]=dp[1]+dp[0]=2$；$dp[3]=2+1=3$；$dp[4]=3+2=5$；$dp[5]=5+3=8$；$dp[6]=8+5=13$；$dp[7]=13+8=21$。7 级台阶共 21 种走法。

排除法：$13$ 是 $dp[6]$；$34$ 是 $dp[8]$；$14$ 是常见手算错误（$13+1$）。

规则：分类计数的两条纪律——「不重」：按最后一步分类，两类没有交集；「不漏」：任何到达第 $i$ 级的走法，最后一步只能是 1 或 2，必属于其中一类。

考点：DP 转移方程正确性的论证（分类计数）。

解析：任取一种到第 $i$ 级的走法，看它最后一步：若跨 1 级，前面必然是「到第 $i-1$ 级」的某种走法；若跨 2 级，前面必然是「到第 $i-2$ 级」的某种走法。一个走法不可能既最后跨 1 级又最后跨 2 级，所以不重；每种走法都有确定的最后一步，所以不漏。相加即全部。

排除法：「数字恰好相加」是巧合不是理由；「背规律」没解释为什么；「自动去重」DP 不会自动去重，不重是因为分类互斥。

规则：三步阶梯推 $dp[i] = dp[i-1]+dp[i-2]+dp[i-3]$，$dp[6] = 24$。

考点：转移方程随「走法集合」扩展。

解析：最后一步可以是 1、2、3 级三种，所以三类相加。$dp[3]=dp[2]+dp[1]+dp[0]=2+1+1=4$；$dp[4]=4+2+1=7$；$dp[5]=7+4+2=13$；$dp[6]=13+7+4=24$。

排除法：$13$ 是 $dp[5]$；$44$ 是 $dp[7]$；$20$ 是错误的手算。

规则：能走 1、2、3 级，最后一步有三类，转移是三项相加。

考点：转移方程与走法集合的对应。

解析：最后一步跨 1 级来自 $dp[i-1]$，跨 2 级来自 $dp[i-2]$，跨 3 级来自 $dp[i-3]$，三类互斥且完备，所以三项相加。

排除法：两项相加漏掉了跨 3 级的走法；乘法变成「每步乘起来」的错解；max 是求最优不是数方案。

规则：状态定义要「自洽且方便转移」——dp[i] = 前 $i$ 家能偷的最大金额，第 $i$ 家偷不偷由转移决定。

考点：最优类 DP 的状态定义。

解析：定义成「第 $i$ 家必须偷」会让转移被迫「跳一家偷一家」，还要比较两种方案，很不方便；定义成「前 $i$ 家的最优值」后，转移只需要在「偷第 $i$ 家」「不偷第 $i$ 家」间取大。

排除法：「第 $i$ 家必须偷」限制了状态、写不出干净转移；「第 $i$ 家现金」是输入数据；「方案数」是计数问题的口径，本题求最大金额。

规则：dp[i] = dp[i-1] + a[i] 意味着「第 $i-1$ 家和第 $i$ 家都偷」，直接违反相邻约束。

考点：转移方程必须编码全部约束。

解析：dp[i-1] 的最优方案里很可能已经偷了第 $i-1$ 家，再加第 $i$ 家就相邻了。用 {6,2,8,4} 验算：正确解是偷 6 和 8，共 $14$（或偷 2+8+4 非法、偷 6+8=14 最优）；错误写法算出 $6+2+8+4=20$，显然不可行。转移必须把「偷第 $i$ 家就跳过第 $i-1$ 家」写进去。

排除法：「结果偏小」方向反了，这个错误结果是偏大（虚高）；「负数」「越界」与相邻约束无关。

规则：$dp[0]=6$、$dp[1]=6$、$dp[2]=14$、$dp[3]=14$，输出 $14$。

考点：打家劫舍转移的数值追踪。

解析：$dp[0]=6$；$dp[1]=\max(6,2)=6$；$dp[2]=\max(6,\ 6+8)=14$（偷 6 和 8）；$dp[3]=\max(14,\ 6+4)=14$（偷 6 和 8 仍最优，偷 2 和 4 只有 6）。

排除法：$20$ 是错误写法（每家都偷）的结果；$12$ 漏算了 8；$16$ 是 $6+8+2$ 的误加（相邻非法）。

规则：对第 $i$ 家只有「偷 / 不偷」两种决策，分别对应两个子问题，最优 = 两者取大。

考点：决策类 DP 的「选 / 不选」二分支。

解析：不偷第 $i$ 家：问题退化成「前 $i-1$ 家怎么偷最优」，即 $dp[i-1]$。偷第 $i$ 家：第 $i-1$ 家不能偷，最优是「前 $i-2$ 家的最优 + 第 $i$ 家」，即 $dp[i-2]+a[i]$。两者覆盖全部可能且互斥，取大即答案。

排除法：「先加起来」等于让相邻两家都偷；max 与负数无关（打家劫舍金额本来就是非负）；「平均值」没有任何最优性保证。

规则：楼顶在第 $n$ 级之后，最后一步可以从第 $n-1$ 级（已付 $dp[n-1]$）跨上来，也可以从第 $n$ 级（已付 $dp[n]$）跨上来；两者取小。

考点：最小花费爬楼梯的终点口径。

解析：dp[i] 表示「到达第 $i$ 级并付清第 $i$ 级费用」。楼顶不收费，站在第 $n$ 级或第 $n-1$ 级都能一步到顶（一次跨 1 级或 2 级）。所以答案是到达这两个位置的最小花费，即 min(dp[n], dp[n-1])。若只返回 dp[n]，当 dp[n] > dp[n-1] 时就丢了更优方案。

排除法：dp[n] 并不必然更大（要看数据）；「下标从 0」与返回逻辑无关；溢出与 min 无关。

规则：dp[1] 是「到达第 1 级的最小费用」，第 1 级的费用是 cost[0]，必须显式付；默认 0 相当于第 1 级免费。

考点：边界初值的正确设定。

解析：整个递推从 dp[1] 出发：dp[2] = min(dp[1], dp[0]) + cost[1]。若 dp[1] 误为 0，则 dp[2] 也偏小，逐级传递下去，最终答案整体偏小。初值错一，全盘皆错，且程序不报错。

排除法：漏写这行照样能编译（数组已初始化）；默认 0 不等于 cost[0]（除非数据恰好为 0）；dp[1] 被 dp[2]、dp[3]…… 一路用到，不是只被用一次。

规则：滚动数组把空间从 $O(n)$ 压到 $O(1)$，时间仍是 $O(n)$（每个状态还是要算一次）。

考点：滚动数组的优化维度。

解析：空间优化的原理是「当前状态只依赖少数几个更早状态」，其它更早的值用完就丢。斐波那契只用前两个，两个变量足够。注意它不省时间——每个 $dp[i]$ 仍然要算一次，只是不存下来而已。

排除法：时间没变，还是 $O(n)$；「时间和空间都优化」错在时间项；「写法不同」错，空间确实从 $n$ 变成常数。

规则：两变量滚动模拟斐波那契，循环结束时 b 等于 $f(7) = 13$。

考点：滚动数组的数值追踪。

解析：初值 a=0, b=1 表示 $f(0), f(1)$。每轮 c = a+b 算下一个数，a=b、b=c 后移。i=2 后 b=1（$f(2)$）；i=3 后 b=2（$f(3)$）；i=4 后 b=3；i=5 后 b=5；i=6 后 b=8；i=7 后 b=13。输出 13。

排除法：$8$ 是 $f(6)$（少跑一轮）；$21$ 是 $f(8)$；$34$ 是 $f(9)$。

规则：空间能否压缩取决于「依赖窗口」——只依赖最近 $k$ 个状态就能用 $k$ 个变量滚动。

考点：滚动数组的适用条件。

解析：算 $dp[i]$ 时，$dp[i-3]$ 及更早的已经不可能再被任何未来状态用到（$dp[i+1]$ 只需 $dp[i]$、$dp[i-1]$），所以可以随时丢弃。这就是滚动数组的本质：依赖关系决定了需要保留的窗口大小。

排除法：数值大小与存储方式无关；「数组浪费内存」不是理论依据；编译器不会自动做这种优化。

规则：贪心在每层只留一条「看起来最好」的路，可能把真正的最优路丢在路口。

考点：局部最优不等于全局最优。

解析：顶点 7 往下看，右下的 8 比左下的 3 大，贪心会走 8 那支。但最优路线 7→3→8→7→5 的和是 30，而 7→8 那支整条最多 29（7→8→1→7→5 或 7→8→1→7→5=28、7→8→0→4→5=24……）。贪心在第一层就丢了最优解。DP 的做法是「每层每个位置都算到达它的最大和」，把所有路都保留下来。

排除法：行数奇偶与算法无关；「漏最后一行」贪心恰恰会走到最后一行，问题是路径不对；「方向相反」无稽之谈。

规则：自底向上把 dp[i][j] 定义为「从 $(i,j)$ 出发到最后一行的最大和」：dp[i][j] += max(dp[i+1][j], dp[i+1][j+1])。

考点：数字三角形的状态定义与转移方向。

解析：从 $(i,j)$ 只能去左下 $(i+1,j)$ 或右下 $(i+1,j+1)$，所以到达末行的最大和 = 本格数字 + 两个子位置的最大和取大。逐层从下往上填，最后 dp[0][0] 就是全图最大和。

排除法：「从顶点走到 $(i,j)$」是自顶向下的定义；「数字本身」是输入；「最少步数」是另一类问题。

规则：自底向上逐层合并，a[0][0] = 30。

考点：数字三角形自底向上的数值追踪。

解析：第 4 行原样 {4,5,2,6,5}；第 3 行 {2,7,4,4} 各加下方两格较大值：$2+\max(4,5)=7$、$7+\max(5,2)=12$、$4+\max(2,6)=10$、$4+\max(6,5)=10$；第 2 行 {8,1,0} 变 $8+\max(7,12)=20$、$1+\max(12,10)=13$、$0+\max(10,10)=10$；第 1 行 {3,8} 变 $3+\max(20,13)=23$、$8+\max(13,10)=21$；第 0 行 $7+\max(23,21)=30$。

排除法：$28$、$29$ 是贪心路径的答案；$27$ 漏了一条大支路。

规则：小三角自底向上合并得到 21。

考点：自底向上 DP 的手算追踪。

解析：末行 {4,1,8,3}；第 2 行 {6,5,7} 变 $6+\max(4,1)=10$、$5+\max(1,8)=13$、$7+\max(8,3)=15$；第 1 行 {3,4} 变 $3+\max(10,13)=16$、$4+\max(13,15)=19$；第 0 行 $2+\max(16,19)=21$。路径 2→4→7→8。

排除法：$18$ 是另一条小路的和；$19$ 是 a[1][1] 的中间值；$20$ 是常见手算漏项。

规则：把 max 换成 min 就变成「最小路径和」，同一框架改一个函数名即可。

考点：DP 求最大/最小只差目标函数（max/min）。

解析：末行 {4,5,2,6,5}；第 3 行 {2,7,4,4} 变 $2+\min(4,5)=6$、$7+\min(5,2)=9$、$4+\min(2,6)=6$、$4+\min(6,5)=9$；第 2 行 {8,1,0} 变 $8+\min(6,9)=14$、$1+\min(9,6)=7$、$0+\min(6,9)=6$；第 1 行 {3,8} 变 $3+\min(14,7)=10$、$8+\min(7,6)=14$；第 0 行 $7+\min(10,14)=17$。

排除法：$16$ 少算一格；$19$、$21$ 是最大路径方向的结果。

规则：记忆化返回前先落盘（存进 memo），函数返回的就是 memo 里的值。

考点：记忆化搜索的「判空 + 落盘 + 返回」三件套。

解析：memo[i][j] != -1 判空（-1 表示还没算过）；算完先 memo[i][j] = ... 存起来，再 return memo[i][j]。这样下次再问同一个 $(i,j)$ 直接命中缓存，不再递归。

排除法：返回 a[i][j] 丢掉了下方的最大和；返回 memo + a 重复加了本格；返回 dfs(i-1,j) 方向反了（自底向上才往上走）。

规则：判空标记必须是一个「合法结果永远取不到」的值；负数在本题（全正数）不会出现，是安全标记。

考点：记忆化判空标记的选择。

解析：若结果可能为 0，用 0 当标记就会造成「已经算过且答案是 0」的状态被当成没算，导致重复递归甚至死循环。数字三角形全为正数，答案至少是某个数字，所以 -1 安全。

排除法：快慢与 -1/0 无关；数组 int memo[5][5] 若不初始化是垃圾值，正确代码会先 memset 或显式初始化；-1 当然能存数值，它就是「未算过」这个特殊值。

规则：非底层状态 $1+2+3+4 = 10$ 个，每个状态第一次被问到时才真正计算，之后全部命中缓存。

考点：记忆化把「每个状态只算一次」落实在具体数字上。

解析：第 0 行 1 个、第 1 行 2 个、第 2 行 3 个、第 3 行 4 个，共 10 个非底层格子需要算 memo[i][j] = ...；第 4 行 5 个直接 return a[4][j] 不走计算行；任何格子算过一次后，再被上层要时都从 memo[i][j] != -1 直接返回。

排除法：15 是把底层直接返回也算成「计算」；25 是朴素递归的调用量级；5 是只数了底层。

规则：状态数 = 三角形格子数 $O(n^2)$，每状态 2 种转移，总 $O(n^2)$。

考点：记忆化搜索的复杂度口径。

解析：$n$ 行三角形有约 $n^2/2$ 个格子，每个格子的 dfs 只真正计算一次，每次做两次递归调用（其中第二次大概率命中缓存）。所以总时间 $O(n^2)$。若用朴素递归不加 memo，是 $O(2^n)$。

排除法：$O(2^n)$ 是朴素递归；$O(n)$ 低估了（每个格子都要算）；$O(n^3)$ 没有出处——状态 $O(n^2)$、每状态常数次转移。

规则：DP 的「是什么」由状态定义和转移方程决定，和「怎么算」（循环还是递归）无关；记忆化只是给递归套了缓存。

考点：自底向上与自顶向下的等价性。

解析：两个版本的状态 dp[i][j] 都表示「从 $(i,j)$ 到末行的最大和」，转移都是 + max(下方两格)。自底向上循环先算下层再算上层；记忆化从顶层递归下去问，碰到没算的就算，靠 memo 保证每个格子只算一次。计算图相同、方程相同，结果必然相同。

排除法：递归不会退化成循环；编译器一般不做这种递归→循环优化（尾递归才行）；「用同一个数组」不是等价的原因。

规则：同阶复杂度、常数差异；记忆化在「状态大量用不到」的场景更省。

考点：两种实现方式的取舍。

解析：数字三角形所有格子都会用到，两者都是 $O(n^2)$，递推省去函数调用常数略快。但有的问题状态空间很大而实际会访问到的很少（比如搜索树的稀疏访问），记忆化只算访问到的，递推却要填满整张表——那时记忆化更快。

排除法：差距只是常数；「快一个数量级」都说过头；记忆化当然能处理最优化问题。

规则：记忆化只对「重叠子问题」有收益——不重叠时存了也没人再用，白存。

考点：记忆化提速的前提。

解析：记忆化把每个状态的答案存下来供复用。若状态从不重复（每个子问题只被要一次），缓存全是浪费。数字三角形、斐波那契都大量重叠，所以记忆化收益巨大。

排除法：递归深度只受栈限制，与提速前提无关；正负、全局变量都无关。