企业官网建设流程全解析

信息学奥赛一本通里的 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) 上，你只有两个选择，要么走向正下方的 (i+1, j)，要么走向右下方的 (i+1, j+1)。既然 dp[i+1][j] 和 dp[i+1][j+1] 已经代表了从下一层两个候选点出发的最优和，那你当然是取两者之中较大的那个，再加上自己这一格的数字。写成式子就是：

dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])

而最底层的 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[i+1][j], dp[i+1][j+1])。

两者的核心区别在于"答案在哪里"。自顶向下算完之后，最终答案散落在最后一行的 n 个位置里，你还要额外遍历一遍取最大值。而自底向上算完之后，答案直接就落在 dp[1][1] 上，塔尖的位置天然就是终点。少写一个 for 循环事小，更重要的是自底向上的状态定义更符合"路径往下延伸"的物理直觉。

2.2 转移方程推导中的细节

推导转移方程时，有几个点特别容易想当然，一旦含糊后面就会出错。

第一个细节是"取 max 的对象"。自底向上时，你在 (i, j) 这个点，能去的只有 (i+1, j) 和 (i+1, j+1)，不可能跳到 (i+1, j-1) 或更远的地方，因为题目规定每一步只能走到下一层相邻的两个点。所以 max 里就是这两个，别多想。

第二个细节是"状态的完备性"。为什么 dp[i][j] 足以支撑后续决策？因为从 (i, j) 往下怎么走，只跟"当前在哪个位置"有关，跟"你是从塔尖怎么一路走过来的"完全无关。这一点非常重要，它叫无后效性。哪怕有两条不同的路都能走到 (i, j)，只要位置相同，后续能取得的最优和就一样。正因为有这条性质，我们才能把每个位置的计算结果拿来复用，而不必枚举所有路径。

第三个细节是"加法的位置"。dp[i][j] 一定等于 a[i][j] 加上子问题的最优解，因为 (i, j) 这个点的数字是无论如何都要计入的，它不参与选择，只参与累加。搞混这点，写成 max(dp[i+1][j], dp[i+1][j+1]) 而忘了加 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 行时第 i+1 行已经全部变成了"从各自位置出发到底部的最大和"，数据已经就绪。

我在带新人的时候，几乎都让他们先把这个版本背下来。它的好处是变量少、边界干净、不需要判断左右两侧，写完基本不会错。

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[i+1][j], dp[i+1][j+1])，计算第 i 行时只依赖第 i+1 行，所以完全可以用一个一维数组 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[j+1] 都还是"下一层"的旧值，因为 j 是从小到大更新的，dp[j+1] 还没被本层覆盖，dp[j] 也还没轮到自己被覆盖。等 dp[j] 更新完，它才变成当前层的值。所以一整轮下来，dp 数组始终保持"下一层状态"，空间从 O(n²) 降到 O(n)。这就是经典的滚动数组套路，很多更高阶的 DP 题都在用同一招。

3.4 三种写法的复杂度与适用场景对比

选择建议是：日常练习用二维原地修改，写起来快、想清楚就对了；做大作业或者遇到 n 很大的题，换成滚动数组。自顶向下那版主要是为了帮你建立双视角，真比赛不太会选它，因为多一遍最后扫描，还多一堆边界判断。

4. 调试实录：那些年踩过的边界坑

4.1 下标从 0 还是从 1 开始

这道题强烈建议下标从 1 开始。原因有二：一是金字塔的"第 i 行有 i 个元素"这个规律用 1 起始写起来最顺，循环上界直接就是 i；二是自顶向下转移要用 dp[i-1][j-1]，如果从 0 开始，j=0 时 j-1 变成 -1，越界问题更绕。

从 0 开始当然也能写，只是边界判断会变成 j==0 和 j==i-1 两种特殊情形，可读性差一截。我当年第一次写这道题图省事用了 0 起始，结果调了半天才发现最右列取到了上一行末尾的元素。改成 1 起始之后一口气就过了。

4.2 数组到底该开多大

一本通这道题常见的数据规模是 n 不超过 1000，所以开到 a[1005][1005] 就足够。但有几个细节要盯住。

一是二维数组不建议在 main 里面定义。1005×1005 的 int 数组大约 4MB，局部变量放在栈上很容易爆栈，导致程序毫无征兆地崩溃。养成把它定义成全局变量的习惯，全局变量在静态存储区，空间宽松得多。

二是如果题目规模写在别的范围，比如 n 最大 5000，你按照 1005 开数组就会读写越界，程序可能输出随机值或者直接段错误。读题时务必把数据范围抄下来，对着范围开数组，宁大勿小，但别大得离谱造成内存超限。

三是如果用了 long long，内存直接翻倍。这道题的和值范围不大，int 通常够用，但如果你不确定数据规模，或者题目注明了数字很大，果断上 long long，4MB 和 8MB 的差别换来的是不会溢出的安心。

4.3 常见错误速查表

把大家最常犯的错误整理成一张表，考前扫一眼能救命。

4.4 我自己的调试小习惯

分享几个我踩坑之后养成的习惯，成本极低，收益极高。

第一，读完输入先在脑子里或者纸上跑一遍样例，确认数据读对了。很多时候答案不对不是算法错，而是读入格式理解错了，比如题目是每行 i 个数你却按每行 n 个读了。

第二，把 dp 数组在中间过程打印出来。以样例为例，跑完之后打印整个金字塔，你应该看到 a[1][1] 变成 30，a[2][1] 变成 22，a[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。这个小习惯我用了很多年，几乎每次卡壳的时候都能帮我省下大把调试时间。