数字三角形这道题在竞赛圈里的地位大概相当于学游泳时的第一口水——呛过之后你才算真正开始。信息学奥赛一本通 1258也就是第九章动态规划里的例 9.2 数字金字塔几乎是人手一份的入门题。它一共不到二十行核心代码却把动态规划的四要素——状态定义、状态转移、边界处理、答案提取——完整地塞了进去。很多同学刷了几十道题仍然说不清什么叫状态而这道题恰好能把这个抽象概念落到纸面上。下面我把这道题从暴力枚举开始一层层拆到一维数组压缩再补上几个版本的实现和实际踩过的坑。无论你是刚接触动态规划的新手还是带学生的教练应该都能从里面找到能直接用的东西。1. 这道题凭什么成为动态规划的第一课1.1 先算一笔账暴力枚举到底会慢成什么样数字金字塔的规则很简单从塔顶出发每一步只能走向正下方或右下方的相邻点一直走到最底层问路径上数字之和最大是多少。新手看到所有路径四个字第一反应往往是深度优先搜索把每条路都试一遍。这条路在逻辑上完全正确问题是它撑不住数据规模。塔有 n 层时从顶到底每一步都有两个分支总路径数是 2 的 (n-1) 次方。n 等于 20 的时候大约是五十万条机器还能扛n 等于 30 就是五亿条一秒内跑不完等到 n 等于 1000这个数字大到连用科学计数法写出来都嫌占地方宇宙寿命都跑不完。你会发现搜索树这个词用得非常贴切因为它真的会长成一棵指数级膨胀的树。关键观察在于这棵搜索树里有大量重复。同一个位置可能从左上角绕过来一次从右上角绕过来一次而这两条路之后的走法完全相同。重复计算的是同一批子问题砍掉它们复杂度立刻从指数级掉到多项式级。这就是动态规划存在的全部理由——不是技巧炫技而是对重复子问题的复用。1.2 题目到底在问什么把文字翻译成数学一本通 1258 的输入格式是第一行一个正整数 n 表示层数接下来 n 行第 i 行有 i 个整数构成金字塔。输出一行的整数表示从顶到底所有合法路径中数字之和的最大值。这里有两个容易被忽略的限定条件。第一每一步只能走到正下方或右下方意味着从位置 (i, j) 出发只能到 (i1, j) 或 (i1, j1)路径长度固定为 n不能横着走也不能往回走。第二到底部任意处结束说的是终点不限定在最后一行的哪一列只要到了第 n 行就算走完答案要在第 n 行的 n 个值里取最大。这两点决定了后面状态转移方程的形状。用样例看一眼就更清楚了。输入五层金字塔分别是 1311 812 7 266 14 15 812 7 13 24 11。最优路径是 13 到 8 到 26 到 15 再到 24加起来 86。这条路的每一步都是在往下和往右下之间做的取舍而且每一次选择都会影响后面能走到的位置范围这正是它不能用简单贪心解决的原因——只看眼前最大很容易走进一个后续全是小数字的死角。1.3 从例 9.2 的位置看一本通这一章的编排思路一本通的第九章把动态规划放在搜索、贪心之后讲是有讲究的。搜索解决所有方案,贪心解决局部最优能推全局最优,而动态规划处理的是那种局部最优推不出全局最优、但子问题答案可以被复用的中间地带。数字三角形恰好是这条分界线上的标尺题。它的编号是 1258紧跟在 1257 之类的入门例题后面属于例题而非练习题说明编写者的意图是让读者在老师或教材的引导下把范式走一遍而不是自己硬啃。所以刷这道题的正确姿势不是做出来就行而是要把它的推导过程写在本子上状态是什么、转移为什么长这样、边界在哪、答案怎么取。这几个问题答不上来后面做最长上升子序列、背包、区间 DP 的时候只会越做越糊涂。可以说1258 这道题本身的价值不在代码而在于它逼你第一次完整地思考了动态规划。2. 状态与转移把金字塔想透的关键三步2.1 状态的选定为什么要盯住走到某点的最大和动态规划的第一步是定义状态而状态定义的核心原则是它要能唯一确定后续决策所需要的信息。在这个问题里你走到 (i, j) 之后后面能怎么走只取决于你在第几层第几列跟你前面是怎么绕过来的完全无关。这就是无后效性,也是能上 DP 的前提。那状态里该存什么最自然的想法是存从塔顶走到 (i, j) 的所有路径中和最大是多少,记作 f[i][j]。为什么不存当前和或者所有可能的和因为后者信息量太大且大部分是无用的。你到 (i, j) 时如果有一条和更大的路那条路后续的走法选择完全一样所以小和的那条路永远不可能翻身。这就叫最优子结构——大问题的最优解由子问题的最优解拼出来。反过来说如果题目改成了求所有路径中和为某个特定值的方案数那么 f[i][j] 里就必须存一个计数数组状态空间会变大很多。可见状态定义不是拍脑袋定的是被问题问的东西反过来约束的。理解这一点比背十道题的转移方程都管用。2.2 转移方程的推导一次逆向思考的胜利确定了 f[i][j] 的含义接下来要找它和更小规模子问题的关系。这里有个方向选择的问题是从上往下推还是从下往上推。自顶向下的想法是f[i][j] 等于 a[i][j] 加上走到它的两个前驱中较大的那个。也就是 f[i][j] a[i][j] max(f[i-1][j-1], f[i-1][j])当 j 等于 1 时只有一个前驱正上方当 j 等于 i 时也只有正左上方一个前驱。这个式子成立但边界要单独处理而且最终答案还得在第 n 行里再扫一遍取最大。自底向上的想法更巧妙f[i][j] 表示从 (i, j) 出发走到最底层能获得的最大和那么 f[i][j] a[i][j] max(f[i1][j], f[i1][j1])而 f[n][j] 就等于 a[n][j] 本身直接就是已知量。答案也顺理成章地落在 f[1][1] 上不用再扫一遍。两个方向在数学上等价但自底向上的版本少了两处边界特判答案位置也更固定。这种把问题倒过来问的思路在很多题目里都能省下一堆 if 分支。我个人带学生时习惯先让他们按自顶向下写一遍感受一下边界有多烦再引出自底向上这样印象会深得多。2.3 用递推顺序保证用到的已经算好动态规划还有一个容易被忽略的条件计算顺序必须保证算 f[i][j] 时它依赖的状态都已经就位。自底向上版本里f[i][j] 依赖第 i1 行所以循环要从第 n-1 行开始逐行往上第 i 行内部从左到右或者反过来都行因为同一行之间没有依赖。这个顺序一旦写反读到的就是还没赋值的垃圾数据。我见过不少同学的代码逻辑完全正确却怎么都跑不出正确答案最后发现是循环写成从第一行到第 n 行等于在用空值推导。这类错误不会报编译错也不会报运行时错只会安安静静地给出一个错误答案排查起来相当费劲。所以写 DP 的时候我建议先在纸上把依赖箭头的方向画出来再确定循环的走向比盯着屏幕空想快得多。这一步花的两分钟往往能省掉半小时的调试。3. 代码落地三个版本的实现与取舍3.1 基础二维 DP把推导一比一翻译成代码先看最直白的写法也是我最推荐新手写的第一版。它和上面的推导几乎逐字对应方便对照检查。#include iostream #include algorithm using namespace std; const int MAXN 1005; int a[MAXN][MAXN]; int main() { int n; cin n; for (int i 1; i n; i) for (int j 1; j i; j) cin a[i][j]; // 自底向上从倒数第二行开始往上推 for (int i n - 1; i 1; --i) for (int j 1; j i; j) a[i][j] max(a[i 1][j], a[i 1][j 1]); cout a[1][1] endl; return 0; }这里我直接把答案累加回了原数组 a省掉了单独开 f 数组的空间。因为每算完一行下面那一行就再也不需要了原地修改不会破坏后续计算。这种滚动覆盖的写法在空间紧张时很好用代价是原数据被破坏如果你需要还原路径就不能这么干。关于数组大小按一本通的常见数据范围 n 不超过 1000、每个格子是两位以内的非负整数来估算最大和不会超过 10 万量级int 绰绰有余。开数组的时候顺手开大一点比如 1005 乘 1005能挡掉不少因为差一行导致的越界。至于内存1005×1005 个 int 大约 4MB一般的题目内存限制都放得下。3.2 一维数组压缩把空间从平方降到线性上一版的空间复杂度是 O(n²)如果 n 开到 3000 甚至更大就会开始吃紧。观察转移方程会发现算第 i 行只用到第 i1 行的数据更早的行早就不用了。既然如此为什么还要把整个三角存下来#include iostream #include algorithm using namespace std; const int MAXN 1005; int a[MAXN][MAXN]; int dp[MAXN]; int main() { int n; cin n; for (int i 1; i n; i) for (int j 1; j i; j) cin a[i][j]; // 最底层的初始值 for (int j 1; j n; j) dp[j] a[n][j]; for (int i n - 1; i 1; --i) for (int j 1; j i; j) dp[j] a[i][j] max(dp[j], dp[j 1]); cout dp[1] endl; return 0; }这段代码里 dp[j] 在更新前代表从 (i1, j) 出发的最大和,dp[j1] 代表从 (i1, j1) 出发的最大和更新后 dp[j] 变成从 (i, j) 出发的最大和。关键在于内层循环 j 从小到大遍历时dp[j1] 还没被这一轮改过仍然是旧值所以取 max 完全安全。如果写成从大到小就会读到已经被覆盖的数据答案直接错掉。这个循环方向的坑几乎是所有一维 DP 的通病。以后遇到背包问题也会碰到同样的问题记住一句话谁会被覆盖就避开谁。在数字三角形里右邻居不能被提前改所以从左往右扫。还有一点值得说如果输入允许你边读边处理其实连 a 数组都不一定要存只要把最后一行的 dp 单独处理好前面每行读进来就立刻处理。但那样代码可读性会下降不少除非确实卡内存不建议为了省一点空间把逻辑搞乱。3.3 记忆化搜索从搜索自然过渡到 DP如果你是从搜索起步的记忆化搜索可能是最容易接受的写法因为它保留了递归的直觉只是给每个状态加了一张备忘录。#include iostream #include algorithm #include cstring using namespace std; const int MAXN 1005; const int NEG -1000000000; int n; int a[MAXN][MAXN]; int f[MAXN][MAXN]; int dfs(int i, int j) { if (i n) return a[i][j]; // 到达底层递归结束 if (f[i][j] ! NEG) return f[i][j]; // 已经算过直接取用 return f[i][j] a[i][j] max(dfs(i 1, j), dfs(i 1, j 1)); } int main() { cin n; for (int i 1; i n; i) for (int j 1; j i; j) cin a[i][j]; for (int i 1; i n; i) for (int j 1; j i; j) f[i][j] NEG; cout dfs(1, 1) endl; return 0; }记忆化搜索的好处是只计算真正用得到的状态遇到状态空间稀疏的题目能省下不少时间而且不用操心递推顺序。缺点也很明显递归深度等于层数n 等于 1000 时虽然一般不会爆栈但再大就危险了另外每次调用都有函数开销常数比递推大。这里我用了一个负无穷大的哨兵 NEG 来标记没算过。如果你确信所有数字都非负用 -1 当标记也没问题但万一题目变体里出现了负数-1 就会被当成合法答案直接判错。后面第 4 章会专门讲这个坑。3.4 三个版本放在一起看怎么选版本空间复杂度时间复杂度递归风险适合场景二维递推O(n²)O(n²)无新手练习、需要还原路径一维压缩O(n)O(n²)无数据大、内存吃紧记忆化搜索O(n²)O(n²)有状态稀疏、状态定义复杂选择建议其实很简单平时练习写二维递推把思路理顺比赛遇到 n 超过 2000 的同类题换成滚动数组如果状态转移里有大量用不到的分支或者转移条件特别复杂再考虑记忆化搜索。不用刻意追求最省空间可读性在调试阶段的价值远大于那几兆内存。4. 踩坑实录这道题最容易错的六件事4.1 下标从 0 还是从 1必须一开始就定死很多人写这道题时会在下标上反复横跳读入用从 1 开始转移的时候又下意识写成 0 开始结果就是明明思路对、代码看起来也顺偏偏输出一个莫名其妙的小数字。原因是读入时故意留白的第一行第一列全是 0而 0 在非负数据下恰好是最小值于是错误被完美地掩盖成了结果偏小。我的习惯是全程从 1 开始因为这样 (i, j) 的语义和第 i 层第 j 个完全一致读代码时不用在脑子里做减法。数组开 MAXN 时多给几格把第 0 行第 0 列空出来正好当缓冲区也顺便挡住了 j1 越界的风险。这个习惯在后续几乎所有 DP 题里都能继续用。4.2 负数和哨兵值一个藏得很深的雷前面用 -1 或者 0 当未计算标记在本题的标准数据下没问题。但如果你在题库里遇到的变体是数字可以是负数——比如某些学校的改编题——那所有基于非负假设的哨兵就全废了。用一个可能出现的合法值去表示不存在这是状态标记类代码的经典错误。稳妥的做法是额外开一个 bool 型的 vis 数组专门记录这个状态算过没有和状态值本身彻底分开。代价是多一倍内存换来的是逻辑上的干净。另外如果数字可能为负所有路径和最大的答案也可能是负的初始化答案的时候别顺手写个 ans 0得写成负无穷。4.3 本地自测和在线评测的差异别只信自己机器这道题在很多学校的教学管理平台、在线题库里都有收录有些平台会额外加数据点比如 n 等于 1 的退化情况。n 等于 1 时最优答案就是唯一的那个数此时你的自底向上循环从第 0 行开始压根不会执行直接输出 a[1][1]逻辑上没问题但如果数组没初始化或者读入写错就会输出随机值。我建议本地测试至少准备三组数据n 等于 1 的边界、样例的五层数据、以及一组自己手算过的十层数据。手算十层不现实那就写个暴力搜索程序当对拍器随机生成小数据跑个几百组两边结果一致再提交。这个对拍习惯看起来笨却是赛前最省时间的做法比盯着代码找逻辑错误高效得多。4.4 常见问题速查表现象可能原因排查方法输出 0 或很小的数数组未初始化、下标从 0 开始错位打印第 1 行数据检查读入结果比正确答案小一点循环方向写反读到被覆盖的旧值检查自底向上是否从 n-1 递减程序运行时崩溃数组开小、递归深度超限数组统一开大 5 格递归改递推样例过了但评测不过边界数据n1或负数数据补测 n1确认哨兵值安全内存超限多次开大数组、n 达到数千用一维滚动数组替换二维4.5 关于还原路径这个附加需求有些老师会在这道题后面追问一句把这条最优路径打印出来。这时候你会发现之前原地覆盖 a 数组的写法不灵了因为原始数据被破坏没法倒推。正确做法是额外开一个 f 数组存状态再用一个记录选择的数组从 (1,1) 出发往下走每次比较 f[i1][j] 和 f[i1][j1] 谁大就往哪边走。这个附加练习的价值很高因为它逼你区分状态数组和原始数据数组这两个概念。很多同学做动态规划时习惯把所有东西混在一个数组里题目一复杂就乱套。分开存思路立刻清晰代价只是多一点点空间非常划算。5. 从 1258 往外延伸还能这么练5.1 数塔类题目的共同骨架长什么样数字金字塔是数塔类问题的原型这类题有一个统一的骨架一个多阶段的决策过程每个阶段有若干状态状态之间有固定的可达关系求某条路径上的最优值。把数字三角形里的下一层两个位置换成别的连接关系就得到了一大批变体。比如把每层换成任意多个、连边关系用一个图来描述、状态转移改成乘除或者取模运算骨架不变只是表面变了。真正需要你重新思考的是状态是否满足无后效性以及转移是否覆盖了所有合法决策。抓住这两点题目换个外壳你也不会慌。另外提一句搜索混淆的事经常有人把这道题和最短路径问题搞在一起搜看到路径最大就去找弗洛伊德或者别的什么最短路算法。弗洛伊德处理的是图上任意两点间的最短路和这里的分层递推求最大路径和完全是两回事虽然都能用路径这个词描述但一个是在图上做三重循环一个是在分层结构上做线性递推别把它们混成一锅。认准分层、每层只依赖上一层这个特征就不会走错门。5.2 顺着编号往下做的几条练习线如果这道题你写得挺顺接下来可以按两条线往下练。第一条是同一骨架加深找几道数塔变体把连边规则改成不规则的比如某些位置可以斜跨两格、某些位置根本走不通练的是转移方程的灵活改写。第二条是换骨架但同思想直接跳去最长上升子序列和 01 背包前者练以某个位置结尾的状态设计后者练容量维度的状态设计。我自己带学生时的节奏是1258 写完立刻手推一遍状态转移表然后再找两道变体题不许看题解逼自己在纸上把转移方程写出来。这个过程大概花四十分钟效果远比刷十道同类题然后每题看一眼题解要好。动态规划真正难的地方从来不是代码而是把状态和转移想清楚而这个能力只能靠自己先想、再对照来练。最后分享几点个人体会我带过不少从这道题开始入门的学生发现一个规律凡是把状态定义用中文完整写下来、并且能说清为什么不需要记录前面的路径的人后面学背包和区间 DP 都很顺而那些直接抄代码、靠背模板过关的人到第九章后半段就开始崩盘。1258 的价值不在于它有多难而在于它是第一道能让你把抽象概念落地的题。另外一个小技巧是我自己调试 DP 时常用的在转移循环里加一句打印把每一层的状态数组打出来和你在纸上手推的结果逐行比对。数字三角形只有五层的时候手推一遍大概三分钟却能立刻暴露循环方向、初始值、边界这三类错误中的任意一类。这个习惯后来我写任何 DP 都在用省下的时间早就超过那点打印的麻烦。如果还要再往前一步我会建议你把这题的一维压缩版本默写两遍直到不看提示也能写对循环方向为止。因为谁会被覆盖就避开谁这个判断在后面的背包问题里会反复出现早点把它变成肌肉记忆后面能少掉很多头发。