P4726 数字金字塔（提高）

解题思路

第一步：看懂题目。 数字金字塔问题是一个经典的动态规划（DP）入门题。金字塔每一层有若干个数字，从最高点出发，每一步可以走到左下方或右下方的数字，问走到最底层时，经过的数字之和最大是多少。

第二步：想出“自底向上”的递推方法。 我们不看从顶往下怎么走，而是反过来看“如果我要走到某一个格子，最好的前一步在哪里”。设 tri[i][j] 表示金字塔第 i 行第 j 列的数字。从倒数第二行开始，自下往上处理：对于格子 (i,j)，它下面能接的只有 (i+1,j) 和 (i+1,j+1) 两个格子。为了让经过的和最大，自然选择这两个格子里已经积累的和较大的那一个，把这个较大的值加到 tri[i][j] 上。这样 tri[i][j] 就变成了“从 (i,j) 出发到最底层能得到的最大和”。

第三步：答案在哪里？ 这样一层一层往上算，最后 tri[1][1] 就是“从最高点出发能得到的最大和”，也就是答案。比如样例中从 13 出发，走 13→8→26→15→24，和为 13+8+26+15+24=86，正好是样例输出。

第四步：为什么可以这样从下往上算？ 因为每个格子只会被它上面相邻的两个格子用到，它自己算出来的最大和只依赖下面一层的两个值，而这两个值又依赖更下面……形成一条链式的依赖关系。只要保证从下往上算，每个格子的值都是“最终确定”的，递推就正确了。这种“每一步决策只依赖已经算好的子问题”的方法，就是动态规划的核心思想。

第五步：注意边界与数据大小。 最底层每个格子的最大和就是它自己的数字，不用改动。n 最大是 1000，每行最多 1000 个数，每个数最大 100，所以最大和不超过 100000，int 类型足够。数组要开成 1005×1005 并放在全局，避免局部数组太大导致栈溢出。

参考代码

// 数字金字塔：从底部往上递推，每步取左下右下中较大的数相加
#include <iostream>
using namespace std;
int tri[1005][1005];  // 存金字塔，全局数组避免栈溢出
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> tri[i][j];
    // 从倒数第二行往上，每个数加上它下方两个数中较大的一个
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            tri[i][j] += tri[i+1][j] > tri[i+1][j+1] ? tri[i+1][j] : tri[i+1][j+1];
    cout << tri[1][1] << endl;
    return 0;
}

复杂度分析

程序读入时用两层循环处理 n 行数字，递推时也是两层循环从底向上处理，每一层的格子数总共是 1+2+...+n = n(n+1)/2，所以时间复杂度和空间复杂度都是 O(n²)。n 最大是 1000，n² 是一百万，无论时间还是内存都完全在限制之内。