数字金字塔这道题我前后带过好几批学生也在自己的刷题记录里反复翻出来重写过至少四遍。几乎每个人的第一次提交都长一个样从顶点往下走每一步挑下面两个数里大的那个加完输出。样例输入 5 行能跑到 30纯属巧合换一组只有 3 行的数据立刻崩盘。这道题最值钱的地方不在代码而在于它用最小的数据规模把局部最优不等于全局最优这件事钉进了脑子里。它讲的是一类非常基础的动态规划模型读入一张三角形数表从顶点出发每步只能走向正下方或右下方相邻的位置一路到底部任意位置结束求路径上数字之和的最大值。适合刚接触动态规划、DP 递推式还写不利索的同学也适合刷到一半发现自己只会背模板、不会推状态的人回头重新看一遍。1. 把题目规则拆干净再动手写第一行代码1.1 输入输出到底长什么样题目给的输入格式是第一行一个整数 R表示金字塔的层数接下来 R 行第 i 行有 i 个整数中间用空格隔开。输出只有一行就是那个可能得到的最大和。样例的五层金字塔长这样7 3 8 8 1 0 2 7 4 4 4 5 2 6 5样例输出是 30对应的路径是 7 → 3 → 8 → 7 → 5。你能顺着这个走法在图上比划一下从第一行的 7 出发走左下到 3再走右下到 8再走左下到 7最后走左下到 5加起来正好 30。题目里明确写了所有给出的整数都是非负的且不大于 100。R 的上限通常在 1000 这个量级。这两个约束看着不起眼实际上决定了后面很多写法能不能过。数值非负意味着没有负数来捣乱很多边界判断可以偷懒数值上限 100 加上层数上限 1000意味着最大路径和不会超过 100 × 1000 100000一个普通的 int 类型装得下不需要考虑长整型。1.2 路径规则里藏着的两个硬约束第一约束是只能走到正下方或右下方。这一句话直接决定了路径的形状如果你把每一层的下标记作从 1 开始那么在第 i 层第 j 个数字的位置上下一步能去的只有第 i1 层的第 j 个和第 j1 个。位置往下走的过程中下标 j 只会不变或者加一永远不会变小也不会跳过。第二个约束是到底部任意处结束。注意是任意处不是必须落在最后一行的正中间或者某个特定位置。这一点在写自顶向下的递推时特别重要因为最后要取的答案是最后一整行的最大值而不是某个固定位置的值。我见过有人写成输出最后一行的第一个数样例能骗过去一到自己造的数据就错。1.3 贪心为什么会翻车一个三行的反例我给学生讲这道题第一件事就是让他们自己构造一个贪心失败的反例。最简单的一个只要三层9 1 2 9 1 1贪心从 9 出发看到下面 1 和 2选 2到了第 2 行第 2 个位置往下只能到第 3 行的第 2 个或第 3 个都是 1于是路径和是 9 2 1 12。而最优解是 9 → 1 → 9等于 19。差出来的 7 分不是因为贪心算错了而是因为贪心在第 1 步就失去了从第 2 行第 1 个位置可以摸到下一行的 9这个后手。这就是局部最优和全局最优的分岔点。反过来看如果我们强行用搜索来做这道题会是什么规模从顶点到底部每一步有两个选择总共 R-1 步路径总数是 2 的 R-1 次方。R 5 的时候是 16 条路径手算都行R 30 的时候是五亿多条R 1000 的时候这个数字的位数超过 300 位。任何尝试枚举路径的写法在层数上到几十就已经死了。所以这道题必须找一个把重复计算合并掉的办法这就是动态规划登场的理由。2. 状态定义与两条递推路线的手算推演2.1 f[i][j] 的定义说清从哪里来还是往哪里去写 DP 的第一步永远是给状态定一个不含糊的含义。这道题有两种定义方式写法完全不同但都能得到正确答案。定义 A自顶向下视角f[i][j] 表示从顶点出发走到第 i 层第 j 个位置时能取得的最大路径和。它回答的是走到这里为止最多攒了多少。定义 B自底向上视角f[i][j] 表示从第 i 层第 j 个位置出发一路走到最底部能取得的最大路径和。它回答的是从这里开始往下走最多还能拿多少。这两个定义没有优劣只有顺手程度之分。定义 A 的思路贴合人的直觉因为你就是从上往下走的定义 B 的递推式更干净因为它天然避开了第一行只有一格、第二行边界特殊这些麻烦事。下面我把两种都推一遍用样例数据手工填表你可以对着看哪条路更顺。2.2 自底向上递推式干净得让人舒服按定义 B最后一层的每个位置出发往下走其实哪儿都去不了所以 f[R][j] 就等于它自己 a[R][j]。最后一层填完往上一层推第 i 层第 j 个位置加上它下面两个位置里较大的那个 f 值就是自己的 f 值。递推式写成f[i][j] a[i][j] max(f[i1][j], f[i1][j1])循环顺序是 i 从 R-1 倒着到 1j 从 1 到 i。最后答案是 f[1][1]。拿样例从最后一行往上填层数填表结果第 5 行初始4, 5, 2, 6, 5第 4 行2max(4,5)77max(5,2)124max(2,6)104max(6,5)10 → 7, 12, 10, 10第 3 行8max(7,12)201max(12,10)130max(10,10)10 → 20, 13, 10第 2 行3max(20,13)238max(13,10)21 → 23, 21第 1 行7max(23,21)30 → 30答案 30和样例一致。这张表最好自己拿纸笔写一遍比看十遍代码有用。2.3 自顶向下边界才是真正麻烦的地方按定义 A第一行只有一个位置f[1][1] a[1][1]。第 i 层第 j 个位置能从上一层的第 j-1 个或第 j 个位置过来所以f[i][j] a[i][j] max(f[i-1][j-1], f[i-1][j])。看起来只比自底向上多一个下标减一但麻烦在于 j 的取值边界j 1 时没有左上来源j i 时没有正上来源。同样用样例手工填一遍层数填表结果第 1 行7第 2 行37108715 → 10, 15第 3 行810181max(10,15)1601515 → 18, 16, 15第 4 行218207max(18,16)254max(16,15)2041519 → 20, 25, 20, 19第 5 行420245max(20,25)302max(25,20)276max(20,19)2651924最后一行取最大值30对上了。两种方向算出来的中间表并不一样第 4 行分别是 7,12,10,10 和 20,25,20,19但顶点答案相同。这也顺便说明了一件事DP 解的中间状态取决于状态定义不要拿两张表去互相验证中间值。2.4 我在实际写题时怎么选如果时间紧、只求过题我基本都写自底向上。原因是它只有一条递推式没有 if 判断没有不可达标记不用处理负数边界出错概率最低。表里的循环顺序也很稳定外层倒序、内层正序两行代码就写完了。如果是这道题的扩展版本——比如还要求输出具体路径、或者要处理带负数的数据——我反而会用自顶向下或者记忆化搜索。因为自顶向下的填表顺序和人的行走顺序一致回溯路径的时候只需要从最后一行的最大值位置往回倒推思路特别顺。记忆化搜索的优势则在于剪枝友好一旦题目加上不能连续走同一边之类的奇怪限制搜索形态的代码改起来最省事。3. 三份可以直接交的代码从二维到一维3.1 写法一二维数组原地自底向上这是我最推荐的版本逻辑最短也最好讲给别人听。它直接在原数组上做累加不需要额外的 f 数组#include cstdio #include algorithm using namespace std; int a[1005][1005]; int main() { int R; if (scanf(%d, R) ! 1) return 0; for (int i 1; i R; i) for (int j 1; j i; j) scanf(%d, a[i][j]); for (int i R - 1; i 1; --i) for (int j 1; j i; j) a[i][j] max(a[i 1][j], a[i 1][j 1]); printf(%d\n, a[1][1]); return 0; }注意a[i][j] ...这一句当处理第 i 层时第 i1 层的值已经被改造成了从该位置往下走的最大和而第 i 层自己的值还没被动过所以直接用原值 a[i][j] 加上下面两个较大的 f 值是安全且正确的。这个从下往上、逐层覆盖的顺序就是原地 DP 能成立的原因。3.2 写法二一维滚动数组空间从 O(R²) 降到 O(R)把状态压成一维关键在于想清楚 f[j] 在每一轮循环开始时代表什么。按自顶向下的定义进入第 i 层之前f[j] 保存的是第 i-1 层第 j 个位置的答案。更新时f[j] a[i][j] max(f[j-1], f[j])右边的 f[j-1] 和 f[j] 都必须是上一层的旧值所以 j 必须从大到小遍历#include cstdio #include algorithm using namespace std; int a[1005][1005]; int f[1005]; int main() { int R; scanf(%d, R); for (int i 1; i R; i) for (int j 1; j i; j) scanf(%d, a[i][j]); f[1] a[1][1]; for (int i 2; i R; i) { for (int j i; j 1; --j) { int best -1; // 数据非负-1 表示暂时没有合法来源 if (j 1) best max(best, f[j - 1]); if (j i) best max(best, f[j]); f[j] a[i][j] best; } } int ans 0; for (int j 1; j R; j) ans max(ans, f[j]); printf(%d\n, ans); return 0; }这个必须倒着推 j的规则和 01 背包压成一维之后的写法是同一个道理右边用到的旧值一旦被本轮的更新覆盖结果就全乱了。很多人在这里翻车原因不是不会 DP而是没意识到一维数组里的元素会被就地重写。3.3 写法三记忆化搜索好懂但要注意递归深度如果你的递推式一时半会儿推不顺先写记忆化搜索是很好的过渡#include cstdio #include algorithm #include cstring using namespace std; const int N 1005; int a[N][N], f[N][N], R; int dfs(int i, int j) { if (i R) return a[i][j]; if (f[i][j] ! -1) return f[i][j]; return f[i][j] a[i][j] max(dfs(i 1, j), dfs(i 1, j 1)); } int main() { scanf(%d, R); for (int i 1; i R; i) for (int j 1; j i; j) scanf(%d, a[i][j]); memset(f, -1, sizeof(f)); printf(%d\n, dfs(1, 1)); return 0; }它在结构上就是暴力搜索 一个数组记答案对初学者最友好。代价是递归深度等于层数 R这道题 R 最多 1000栈上放得下但如果哪天遇到层数上万的变体这份代码会直接爆栈那时候就该老老实实换成自底向上的循环。3.4 顺手给一份 Python 版和输入处理建议用 Python 写的同学最大的坑是逐行input()在数据量大时偏慢。用sys.stdin.read()一次性读进来再切分会稳很多import sys def main(): data sys.stdin.read().split() p 0 r int(data[p]); p 1 a [] for i in range(r): row list(map(int, data[p:p i 1])) p i 1 a.append(row) for i in range(r - 2, -1, -1): for j in range(i 1): a[i][j] a[i 1][j] if a[i 1][j] a[i 1][j 1] else a[i 1][j 1] print(a[0][0]) main()C 这边scanf和cin在这道题的数据规模下都够用不用特意关同步流。真正需要注意的是读到文件尾和格式空行——有些题库的输入末尾会多一个换行或空格用scanf(%d)会自动跳过空白字符所以不用担心。4. 踩坑实录评测机只给一个 WA不给理由4.1 数组下标从 1 开始还是从 0 开始越界就在一行之间自底向上写法里最内层要访问a[i1][j1]。当 i R-1、j 取到 i R-1 时j1 R而第 R 行确实有 R 个数所以没有越界。但如果你的内层循环顺手写成j i 1立刻就会读到下一层不存在的元素。我的习惯是循环上界严格写j i并且把数组开到 1005×1005留出冗余。顺带算一下内存1005 × 1005 个 int大约 4.04 MB在一个常见的 128 MB 空间限制下毫无压力。这也是为什么这道题用二维数组是最舒服的选择——空间根本不紧张没必要为了省空间牺牲可读性。4.2 自顶向下初始化成 0为什么这次能过、下次就错自顶向下写法的第一行除了 f[1][1]其他位置都是不可达的。如果把它们初始化成 0在这道题里恰好安全因为题目保证所有数字非负任何一条真实路径的和都不会小于 0非法状态不可能被选成最大值。但只要题目把条件改成数字可以是负数初始化 0 就会让一条先走到 -50 再走回来的假路径混进答案。稳妥的做法是用一个足够小的负数比如-0x3f3f3f3f表示不可达别依赖数据非负这个隐含前提。4.3 一维滚动必须倒着推 j正着推就是全错前面提过一次这里再说透一点。第 i 层第 j 个位置的答案依赖上一层i-1 层的 f[j-1] 和 f[j]。如果 j 从小到大遍历等你处理 j 的时候f[j-1] 已经被本轮的第 i 层结果覆盖了于是你拿这一层左边的值当成上一层左边的值用递推链条当场断裂。这种错误最阴的地方在于小数据可能碰巧对R 一大就全盘皆输而且你盯着代码看半天看不出问题因为语法完全正确。4.4 找题解时的检索污染题号和算法都可能对不上自己搜题解的同学应该有过这种体验搜一个题号置顶的结果点进去发现是另一道题。原因很简单同一本书里题号挨得近不同版本的题号编排又可能有出入。我的建议是把样例输入输出当作指纹拿到任何一份题解先用样例核对一遍再决定要不要照着看。另外搜这道题的时候经常会撞上一些算法名词标签比如某些最短路算法也会被一起带出来但那类算法解决的是图上点与点之间最短距离的问题和这里的路径数字求和最大完全不是一回事。看到不匹配的标签别硬套模板先回头确认题目要你求的到底是什么。4.5 关于数据范围的三个自查动作第一看最大答案会不会溢出。这道题上限 100 × 1000 100000int 完全够但如果哪天题目改成乘积最大中间结果可能到 100 的 1000 次方那就必须上高精度或者对数比较。第二看数组要开多大自底向上会多访问一行一列数组按 R3 去开。第三看循环边界要不要加等号这道题的行列下标都是从 1 开始、可取的j i这种地方差一个等号就是 RE 和 AC 的差距。踩坑现象真实根因修复方式样例过、提交 WA贪心思路没换掉确认用 DP 而非每步取大运行时报错退出内层循环上界写成 i1改成 j i数组留冗余结果偏小一维数组 j 正序遍历改成 j 从 i 到 1 倒序答案固定输出 0读入失败或忘了取最后一行最大值检查 scanf 返回值、答案取 max换了带负数的数据就错边界用 0 初始化用 -INF 标记不可达5. 一题多练金字塔模型还能怎么改5.1 加上输出路径本身之后代码形态会变如果题目要求你不仅输出最大和还输出具体走了哪条路自底向上的原地覆盖写法就不好用了因为原数组被改掉了你没法知道当时选的是左边还是右边。解决办法是保留原数组另外开一个 f 数组存 DP 值。填完表后从 (1,1) 出发每一步比较 f[i1][j] 和 f[i1][j1]谁大往哪走走一层输出一层。这个正向回溯的小技巧在很多 DP 题里都能复用比如背包问题求方案、最长上升子序列求具体序列。5.2 反向问题最小路径和与路径计数把 max 换成 min立刻变成最小路径和写法和自底向上完全一样只是取小值。如果改成求有多少条路径能达到最大和就需要在 DP 的同时维护一个计数数组比较两个来源的大小大的那个继承它的计数相等则两边计数相加。这类值 方案数双状态的做法是往后刷题时会反复遇到的标准套路从这里练手正合适。5.3 乘积版0 和负数会把状态定义彻底改写如果变成路径上数字的乘积最大简单的单状态就不够用了。原因是一个很小的负数乘以一个负数会变成很大的正数所以你必须同时记录到此为止的最大积和到此为止的最小积每走一步用新的数去分别更新这两个状态。这个思路和最大乘积子数组是同一套。这个变体很值得亲手写一遍它会让你真正明白状态定义不是随便起的名字它必须覆盖所有可能影响后续决策的信息。5.4 从三角形推广到矩形数字网格去掉三角形形状的限制变成 n 行 m 列的网格每次只能向下或者向右走求从左上到右下的最大路径和——这就是金字塔模型的直系亲属。递推式变成f[i][j] a[i][j] max(f[i-1][j], f[i][j-1])第一行和第一列单独处理。你会发现三角形版本其实是每行长度递增的网格的特例理解了三角形网格版几乎是白送。5.5 空间能不能再压两行甚至一行自底向上版本之所以能把空间压到一行是因为第 i 层只依赖第 i1 层。理论上保留两行当前行和下一行就够了但既然题目空间充裕我会优先选可读性更高的写法。这里想强调的是判断标准当你需要为了省空间而牺牲可读性时先确认空间限制是不是真的紧张。这道题 4 MB 的二维数组完全在安全区内硬压成一维反而增加了出错面。5.6 和最长上升子序列放一起看状态定义的分量就出来了很多同学刷完这道题会觉得自己会 DP 了然后卡在最长上升子序列上。原因就是两者的状态定义难度不是一个量级金字塔题的状态几乎是题目白送的从某位置往下走是天然的分层结构无后效性一眼可见而最长上升子序列需要你自己定义以第 i 个元素结尾还要自己论证这个定义为什么能避免重复计算。所以金字塔题是入门的第一级台阶别把它当成 DP 的全貌。6. 站在讲题人的角度看这道题被放在例题位置的原因6.1 动态规划三要素在这道题里的落点阶段金字塔的每一层天然是一个阶段层数递增层次分明。状态f[i][j] 表示从某个位置开始或到达某个位置的最优值。决策在当前格选择正下方还是右下方两选一。这三个要素在这道题里几乎不需要你费心去抽象题目结构直接摆在那儿。正因为如此这道题承担的教学任务不是教你什么叫 DP而是让你亲眼看到把重叠子问题合并之后效率能差多少个量级。从 2^(R-1) 条路径的枚举到 R(R1)/2 个状态的一遍扫描R 1000 时前者是天文学数字后者只需要五十万次加法。这个对比是讲 DP 时最有说服力的一段素材。6.2 讲无后效性时我最常用的那句话无后效性这个词书上定义很抽象。我给学生讲的时候只说一句当你站在第 i 层第 j 个位置时你只需要知道从上面走到这里最大是多少完全不需要知道你是从左边绕来的还是从右边绕来的也不需要知道你中途经过了哪些格子。前面走过的路怎么走的对后面能拿多少分没有任何影响——这就是无后效性。反过来说如果题目加上路径中不能出现连续两个相同的数字这种条件前面怎么走的信息就必须记录下来状态立刻膨胀那就不再是这道题了。6.3 学生最常见的四类错误与讲评顺序我整理的讲评顺序基本是先讲贪心反例让他们自己造再讲暴力枚举的规模让他们自己估算然后才引出 DP。这个顺序比一上来就讲递推式有效得多。四类高频错误按出现频率排下来是贪心没换掉约占一半、一维滚动 j 顺序写反、自顶向下边界处理错、答案取错位置。错误类型典型表现纠正切入点贪心未替换样例偶尔能过随机数据必错让本人构造三行反例边界遗漏j1 或 ji 处结果异常手算第一行与最后一行循环方向反一维版结果偏小对照 01 背包一维优化答案位置错输出最后一行的首元素强调任意处结束的要求6.4 从这道题往下走下一站该刷什么按我的经验这道题刷完之后最自然的过渡是做数字三角形的最小路径和变体、网格版路径和再往后接背包问题的一维优化。因为背包的一维滚动和这道题的一维滚动是同一个坑先在这里踩过一次、想明白了到背包那里就不会重复栽跟头。反过来如果这道题是抄着题解过的背包那关大概率还要再摔一次。最后分享一个我自己的小习惯每次写完这类 DP 题我都会拿纸把中间状态表手填一遍只填前三层和最后两层。前三层验证初始化对不对最后两层验证边界和最终取值对不对。这个动作花不到两分钟但帮我拦下来的错误比我盯着代码看半小时还要多。尤其是当题目数据范围从 1000 缩到 5 的样例上看起来是对的时手填表几乎是唯一能快速暴露边界问题的办法。