信息学奥赛一本通里的 1258 这道题标题叫数字金字塔很多人第一次看到它时心里是发怵的觉得金字塔这种造型听起来就很唬人。但真上手写过一遍之后你会发现它是动态规划最好的入门砖之一也是把递归思维过渡到递推思维的关键一站。它解决的问题非常具体给定一个由数字堆成的三角形从塔尖往下走每一步只能走向正下方或右下方求一条路径让经过的数字之和最大。适合刚学完一维数组、准备接触 DP 的初学者也适合已经会写但总在边界上翻车的同学回头补课。下面我把这道题从审题、选型、推导到代码落地、调试排查的完整过程拆开讲尽量做到你看完就能自己默写出来。1. 数字金字塔到底难在哪先把题目翻译成算法语言1.1 题目原文拆解与样例复盘一本通 1258 的输入长这样第一行是一个整数 n表示金字塔的层数接下来 n 行第 i 行有 i 个整数构成金字塔的第 i 层。输出只有一行就是从塔尖到底部某一点、沿途数字和最大的那个和值。样例是这样的金字塔7 3 8 8 1 0 2 7 4 4 4 5 2 6 5从顶端 7 出发每一步只能往左下或右下走。题目给出的最优路径是 7 → 3 → 8 → 7 → 5和值是 30。你可以手动验算一下如果第一步走 8 那条分支虽然第二步数字更大但后续被锁死在较小的数上最终反而拿不到 30。这就是这道题的精髓所在眼下的最优并不等于全局最优。很多新手读完题的第一反应是这不就是每次都挑下面那个大的走吗也就是贪心。这个直觉非常自然但它是错的而这道题恰恰是拿来做贪心反例的经典素材。1.2 贪心为什么在金字塔上行不通我们拿样例跑一遍贪心策略站在 7 上下面两个数是 3 和 8贪心会选 8。站在 8 上下面两个数是 1 和 0贪心选 1。站在 1 上下面两个数是 7 和 4贪心选 7。站在 7 上下面两个数是 2 和 6贪心选 6。最后路径是 7 → 8 → 1 → 7 → 6和值是 29比最优解 30 少 1。问题的根子在于贪心只看当前这一步的局部收益它没有向后看的能力。在金字塔里某个位置当前数字大不代表它下面那一整条可持续路径的和也大。换句话说一个节点真正的价值不是它自己的数字而是从它开始往下能取到的最优和。一旦想通这一层你就已经摸到动态规划的大门了。生活里也有很多类似的例子比如爬山时每一步都选最陡的方向很可能把你引到一个小山包而不是主峰。想要全局最优就必须把每个位置往后能走到的最好结果提前算出来然后再做选择。1.3 把路径最大和翻译成状态我们把直觉形式化。定义状态 dp[i][j] 表示从位置 (i, j)第 i 行第 j 列出发一路走到最底部能得到的最大和。注意这个定义的方向是从当前位置往下看而不是从塔尖往上看。这个方向的选择非常关键后面讲写法时会体现它的好处。有了这个定义转移就水到渠成了站在 (i, j) 上你只有两个选择要么走向正下方的 (i1, j)要么走向右下方的 (i1, j1)。既然 dp[i1][j] 和 dp[i1][j1] 已经代表了从下一层两个候选点出发的最优和那你当然是取两者之中较大的那个再加上自己这一格的数字。写成式子就是dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1])而最底层的 dp[n][j] 就是 a[n][j] 本身因为到了底部没法再往下走了。最终答案落在 dp[1][1] 上也就是从塔尖出发的最优和。这一小节先把框架立住下一节我们详细推导为什么这么设计。2. 状态设计为什么 DP 是这道题的正解2.1 两种视角自顶向下与自底向上数字金字塔可以从两个方向来设计状态各有利弊理解它们的差异是真正吃透这道题的分水岭。第一种是自顶向下。定义 dp[i][j] 为从塔尖走到 (i, j) 这个位置时能取得的最大和。转移变成 dp[i][j] a[i][j] max(dp[i-1][j-1], dp[i-1][j])也就是从上一层的两个来源里挑大的。到达位置 (i, j) 只能来自正上方的 (i-1, j) 或者左上方的 (i-1, j-1)。这种视角符合人的自然阅读习惯从塔尖一层层往下推。第二种是自底向上。定义 dp[i][j] 为从 (i, j) 出发到底部能取得的最大和转移是 dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1])。两者的核心区别在于答案在哪里。自顶向下算完之后最终答案散落在最后一行的 n 个位置里你还要额外遍历一遍取最大值。而自底向上算完之后答案直接就落在 dp[1][1] 上塔尖的位置天然就是终点。少写一个 for 循环事小更重要的是自底向上的状态定义更符合路径往下延伸的物理直觉。2.2 转移方程推导中的细节推导转移方程时有几个点特别容易想当然一旦含糊后面就会出错。第一个细节是取 max 的对象。自底向上时你在 (i, j) 这个点能去的只有 (i1, j) 和 (i1, j1)不可能跳到 (i1, j-1) 或更远的地方因为题目规定每一步只能走到下一层相邻的两个点。所以 max 里就是这两个别多想。第二个细节是状态的完备性。为什么 dp[i][j] 足以支撑后续决策因为从 (i, j) 往下怎么走只跟当前在哪个位置有关跟你是从塔尖怎么一路走过来的完全无关。这一点非常重要它叫无后效性。哪怕有两条不同的路都能走到 (i, j)只要位置相同后续能取得的最优和就一样。正因为有这条性质我们才能把每个位置的计算结果拿来复用而不必枚举所有路径。第三个细节是加法的位置。dp[i][j] 一定等于 a[i][j] 加上子问题的最优解因为 (i, j) 这个点的数字是无论如何都要计入的它不参与选择只参与累加。搞混这点写成 max(dp[i1][j], dp[i1][j1]) 而忘了加 a[i][j]是新手最典型的错误之一。2.3 边界与初始化的处理边界处理是这道题另一个隐蔽的坑。自底向上时最下面一行第 n 行的 dp 值就是它自己的数字因为从那一格出发没有下一层可走了。所以初始化 dp[n][j] a[n][j]从这个地基往上递推就行。自顶向下时边界在塔尖和两侧的斜边。塔尖 dp[1][1] a[1][1]这是唯一的初始值。而每一行的最左列 (i, 1) 只能来自正上方的 (i-1, 1)不能来自不存在的 (i-1, 0)每一行的最右列 (i, i) 只能来自左上方的 (i-1, i-1)不能来自不存在的 (i-1, i)。如果不加判断直接用 max就会读到数组的越界位置或者上一行末尾的脏数据这是自顶向下写法的头号 bug 来源。我个人偏向自底向上就是因为它的边界只有一条底边处理起来干净利落不容易在两侧斜边上翻车。2.4 为什么不用最短路算法网上搜这道题的时候经常能看到弗洛伊德算法 信息学奥赛一本通这样的关联词。这里有必要澄清一下数字金字塔虽然长得像图论里的路径问题但它不是个求最短路的图用 Floyd 或者 Dijkstra 是杀鸡用牛刀而且方向也不对。原因有三点。第一这道题求的是路径和最大不是最小目标函数不同。第二如果把每个格子当成节点、每次移动当成有向边那这是个有向无环图DAG根本不存在环任何依赖松弛多轮直到稳定的最短路算法都是浪费。第三也是最关键的题目要求的是从塔尖到底部的所有路径中的最大和这是一个典型的计数类/最优化类 DP状态就是位置本身转移是固定的一步。用 DP 的复杂度是 O(n²)而 Floyd 要 O(V³)V 是点数规模一上来直接爆炸。一句话总结看到路径两个字别条件反射往最短路靠先判断它是有环还是无环、求最大还是最小、约束是不是只能往下走。这三点想清楚算法选型基本就定了。3. 代码落地从二维数组到一维滚动3.1 二维原地修改写法最推荐给初学者对于一本通这道题数据规模通常不大最省心的写法就是读进来之后直接在原数组上自底向上累加省去一个额外的 dp 数组。#include bits/stdc.h using namespace std; int a[1005][1005]; 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; }这段代码的逻辑非常直白第 n 行不动从第 n-1 行往上每一格把下面两格中较大的那个加到自己身上。跑完之后 a[1][1] 就是答案。为什么可以先处理下一行再处理上一行因为我们是从底部往上推的处理第 i 行时第 i1 行已经全部变成了从各自位置出发到底部的最大和数据已经就绪。我在带新人的时候几乎都让他们先把这个版本背下来。它的好处是变量少、边界干净、不需要判断左右两侧写完基本不会错。3.2 自顶向下写法与最后的取最大为了理解两种视角的差别自顶向下的版本也值得写一遍。#include bits/stdc.h using namespace std; int a[1005][1005]; 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 1; i n; i) for (int j 1; j i; j) { if (j 1) a[i][j] a[i - 1][j]; // 最左列 else if (j i) a[i][j] a[i - 1][j - 1]; // 最右列 else a[i][j] max(a[i - 1][j - 1], a[i - 1][j]); } int ans 0; for (int j 1; j n; j) ans max(ans, a[n][j]); cout ans endl; return 0; }注意这里的判断分支最左列只能来自正上方最右列只能来自左上方中间位置才能取两者较大值。这就是我前面说的两侧斜边坑一旦漏掉判断j-1 或者 i-1 就会越界。另外注意初始值 ans 取 0。因为题目里所有整数都是非负的所以 0 作为起点是安全的。如果题目允许负数就得把 ans 初始化成 INT_MIN 或者直接用 a[n][1]这是个容易被忽略的细节。3.3 一维滚动数组的空间优化如果 n 开到 1000二维数组占 1000×1000×4 字节大约是 4MB大多数评测机给的内存是 128MB 或 256MB完全扛得住。但如果 n 开到 10000二维数组就爆了这时候就得上滚动数组。我们观察自底向上的转移方程 dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1])计算第 i 行时只依赖第 i1 行所以完全可以用一个一维数组 dp[] 来滚动把行维度压掉。#include bits/stdc.h using namespace std; int a[1005][1005]; int dp[1005]; 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] 时用到的 dp[j] 和 dp[j1] 都还是下一层的旧值因为 j 是从小到大更新的dp[j1] 还没被本层覆盖dp[j] 也还没轮到自己被覆盖。等 dp[j] 更新完它才变成当前层的值。所以一整轮下来dp 数组始终保持下一层状态空间从 O(n²) 降到 O(n)。这就是经典的滚动数组套路很多更高阶的 DP 题都在用同一招。3.4 三种写法的复杂度与适用场景对比写法空间复杂度边界难度适用场景二维原地修改自底向上O(n²)低只有底边初学者首选数据规模中等二维自顶向下O(n²)高两侧斜边需判断理解双视角用实际少用一维滚动自底向上O(n)中需保留原数组数据规模大或内存紧张选择建议是日常练习用二维原地修改写起来快、想清楚就对了做大作业或者遇到 n 很大的题换成滚动数组。自顶向下那版主要是为了帮你建立双视角真比赛不太会选它因为多一遍最后扫描还多一堆边界判断。4. 调试实录那些年踩过的边界坑4.1 下标从 0 还是从 1 开始这道题强烈建议下标从 1 开始。原因有二一是金字塔的第 i 行有 i 个元素这个规律用 1 起始写起来最顺循环上界直接就是 i二是自顶向下转移要用 dp[i-1][j-1]如果从 0 开始j0 时 j-1 变成 -1越界问题更绕。从 0 开始当然也能写只是边界判断会变成 j0 和 ji-1 两种特殊情形可读性差一截。我当年第一次写这道题图省事用了 0 起始结果调了半天才发现最右列取到了上一行末尾的元素。改成 1 起始之后一口气就过了。4.2 数组到底该开多大一本通这道题常见的数据规模是 n 不超过 1000所以开到 a[1005][1005] 就足够。但有几个细节要盯住。一是二维数组不建议在 main 里面定义。1005×1005 的 int 数组大约 4MB局部变量放在栈上很容易爆栈导致程序毫无征兆地崩溃。养成把它定义成全局变量的习惯全局变量在静态存储区空间宽松得多。二是如果题目规模写在别的范围比如 n 最大 5000你按照 1005 开数组就会读写越界程序可能输出随机值或者直接段错误。读题时务必把数据范围抄下来对着范围开数组宁大勿小但别大得离谱造成内存超限。三是如果用了 long long内存直接翻倍。这道题的和值范围不大int 通常够用但如果你不确定数据规模或者题目注明了数字很大果断上 long long4MB 和 8MB 的差别换来的是不会溢出的安心。4.3 常见错误速查表把大家最常犯的错误整理成一张表考前扫一眼能救命。现象可能原因排查方向输出比正确答案小忘记加 a[i][j] 本身检查转移式有没有漏加当前格输出为随机大数二维数组越界或爆栈数组改全局下标从 1 起程序直接段错误数组在栈上开得太大移到全局或改滚动数组自顶向下答案不对两侧斜边边界未判断补 j1 和 ji 分支输出差一点点输入只读了部分行检查双重循环上界是否为 i换行符处理异常输入混杂空格与换行用 cin 会自动跳过空白4.4 我自己的调试小习惯分享几个我踩坑之后养成的习惯成本极低收益极高。第一读完输入先在脑子里或者纸上跑一遍样例确认数据读对了。很多时候答案不对不是算法错而是读入格式理解错了比如题目是每行 i 个数你却按每行 n 个读了。第二把 dp 数组在中间过程打印出来。以样例为例跑完之后打印整个金字塔你应该看到 a[1][1] 变成 30a[2][1] 变成 22a[2][2] 变成 25 这类中间结果。通过观察中间层你能迅速定位是哪一层开始偏的。第三写一个暴力程序对拍。n 小的时候枚举所有 2^(n-1) 条路径直接求和取最大然后和你的 DP 结果对比。这个技巧对所有 DP 题都通用尤其是你怀疑转移方程写错的时候暴力对拍三分钟就能定位问题。第四注意输入输出的收尾。题目只要一个整数记得加换行如果题目要求多组数据或者有特殊格式一定逐字核对。5. 举一反三从这道题延伸出去的训练思路5.1 同一套模型还能解哪些题数字金字塔是带权 DAG 最长路 DP的最简版本掌握了它一类题都能通吃。比如经典的过河卒、最低通行费、数塔取数、方格取数双线程 DP 版本本质上都是在一个网格或者三角形上做自底向上/自顶向下的递推。区别只在于约束略有不同有的限制只能向右和向下有的限制不能经过障碍物有的要取两次最大值。再往上走一层最长上升子序列、最大子段和、背包系列也都是决策 最优子结构的思路延伸。你会发现学 DP 最有效的方式不是背题而是把每道题的状态定义和转移来源这两点抓出来对比做上十来道自然就形成肌肉记忆了。5.2 滚动数组是个通用大招第 3 节讲的一维滚动不止这道题能用。凡是转移只依赖上一层的 DP基本都能用同一套手法压空间。判定的口诀是看转移方程用到了哪些行如果只有当前行和上一行或者下一行就可以压成一维。但要注意一个坑如果转移里同时用到了上一层和本层已经更新过的位置滚动顺序就必须想清楚是正序还是逆序否则会出现这一层的值把上一层还没用的值覆盖掉的错误。比如 0/1 背包要逆序枚举容量就属于同一类思考。数字金字塔这道题因为只依赖下一层正序逆序其实都行但习惯上我们保持和原方向一致。5.3 给刷题节奏的一点建议最后聊点务实的。很多同学刷一本通的时候容易陷入追求数量的陷阱一天刷十道题但每道都模棱两可。我个人的节奏是一道题至少写两遍第一遍照着思路敲出来第二遍不看题解默写默写时把状态定义先写在注释里再动手。对于 1258 这道题我建议你至少用手写三遍二维原地修改一遍自顶向下一遍滚动数组一遍。三遍下来你对 DP 的理解会比刷十道新题还扎实。另外可以顺手把一本通里相邻的题目比如 1259、1260 一起做了它们大概率是同一模型的变式连着做能形成对比例子记忆更牢。实际写代码的时候我个人的习惯是先把状态定义和转移方程用中文注释写在代码开头再去写循环。这样做的好处是如果你写着写着发现注释里的转移式有漏洞你是在写循环之前就发现问题而不是跑挂了再去翻代码找 bug。这个小习惯我用了很多年几乎每次卡壳的时候都能帮我省下大把调试时间。