【信息学奥赛一本通 C++题解】1258：【例9.2】数字金字塔
信息学奥赛一本通（C++版）在线评测系统
基础算法 第一节 动态规划的基本模型
1258：【例9.2】数字金字塔
小学生的课堂讲解
一、解题思路
同学们，今天我们要解决的是数字金字塔找最大路径和的问题。想象一下，数字金字塔就像一座真正的金字塔，我们要从金字塔的顶端出发，一步一步往下走，每一步只能走到左下方或者右下方的数字，然后把走过的数字都加起来，最后要找到加起来和最大的那条路。
我们可以用一种从下往上“倒着算”的方法。为什么要倒着算呢？因为如果我们从上面开始走，很难知道后面走哪条路能得到最大和。但是从下面往上算的话，我们可以比较每一个数字从它下面两条路走能得到的和，然后选那个大的和加到自己身上。这样一层一层往上算，最后金字塔顶端的数字就是最大路径和啦。
二、解题步骤
- 输入数据：首先，我们要知道金字塔有多少行，然后把金字塔里的每个数字都存到一个表格里。
- 从倒数第二层开始计算：从金字塔的倒数第二层开始，对于这一层的每一个数字，我们看看它下面左下方和右下方的数字，哪个数字加上它下面那条路的最大和更大，就把这个更大的和加到当前数字上。
- 逐层往上计算：按照第二步的方法，一层一层往上算，一直算到金字塔的顶端。
- 输出结果：最后金字塔顶端的数字就是我们要找的最大路径和，把它输出出来。
三、C++代码实现
#include <iostream> // 包含输入输出流的头文件，这样我们才能输入和输出数据
using namespace std;
int main() {
int r; // 定义一个变量 r 来存储金字塔的行数
cin >> r; // 从键盘输入金字塔的行数
int a[1001][1001]; // 定义一个二维数组 a 来存储金字塔里的数字，最多可以存 1000 行
// 输入金字塔里的每个数字
for (int i = 1; i <= r; i++) { // 外层循环控制行数，从第 1 行到第 r 行
for (int j = 1; j <= i; j++) { // 内层循环控制每行的数字个数，第 i 行有 i 个数字
cin >> a[i][j]; // 从键盘输入当前位置的数字
}
}
// 从倒数第二层开始往上计算最大路径和
for (int i = r - 1; i >= 1; i--) { // 外层循环从倒数第二层开始，到第 1 层结束
for (int j = 1; j <= i; j++) { // 内层循环遍历当前行的每个数字
// 比较当前数字下面左下方和右下方的数字，哪个加上它下面那条路的最大和更大
if (a[i + 1][j] > a[i + 1][j + 1]) {
a[i][j] += a[i + 1][j]; // 如果左下方的数字大，就把左下方的数字加到当前数字上
} else {
a[i][j] += a[i + 1][j + 1]; // 如果右下方的数字大，就把右下方的数字加到当前数字上
}
}
}
cout << a[1][1] << endl; // 输出金字塔顶端的数字，也就是最大路径和
return 0;
}
四、知识点总结
- 二维数组：我们用二维数组来存储金字塔里的数字。二维数组就像一个表格，有行和列。在这个问题里，行代表金字塔的层数，列代表每行的数字位置。通过二维数组，我们可以很方便地找到每个数字。
- 循环嵌套：使用了两层循环来输入金字塔的数字，又用两层循环从下往上计算最大路径和。外层循环控制行数，内层循环控制每行的数字个数。循环嵌套可以让我们对二维数组里的每个元素进行操作。
- 动态规划思想：这是解决这个问题的关键思想。我们从下往上，通过比较每个数字下面两条路的最大和，把大的和加到当前数字上，这样逐步得到整个金字塔的最大路径和。动态规划就是把一个大问题分解成很多小问题，先解决小问题，再通过小问题的解得到大问题的解。