P4728 三角形谜题（提高）

解题思路

第一步：看懂题目。 这道题和“数字金字塔”是同一类经典动态规划题。一个由数字组成的三角形，从顶部出发，每一步只能走到左下方或右下方的数字，问走到最底层时经过的数字之和最大是多少。

第二步：用“自底向上”的方法递推。 直接用数组 tri[i][j] 存下三角形第 i 行第 j 列的数字，然后从倒数第二行开始，一层一层往上处理。对于位于 (i,j) 的数字，它往下只能接两个位置：左下 (i+1,j) 和右下 (i+1,j+1)。想知道“从 (i,j) 出发向下走能得到的最大和”，只需要比较这两个子位置已经算好的最大和，选较大的那个，再加到 tri[i][j] 上。这样算完之后，tri[i][j] 就表示“从 (i,j) 出发到最底层的最大和”。

第三步：为什么从下往上算是对的？ 因为任意一个格子的“最优值”只依赖于它下方相邻的两个格子的最优值，而这两个格子的最优值又依赖于更下方的格子……一层一层依赖下去。只要从最底层开始，先算好底层的值（就是它们本身的数字），再往上算，每一步用到的都是已经确定好的答案，最后 tri[1][1] 就是整个三角形的最大路径和。

第四步：举个例子验证。 n=5 的三角形，从顶部的 7 出发，一路选择下方较大的数，最优路径是 7→3→8→7→5，和是 7+3+8+7+5=30，正是样例输出。

第五步：注意读入格式与数据大小。 注意读入的格式：第 2 行起，第 i 行有 i 个数，也就是标准三角形。题目数据 n 最大是 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;
}

复杂度分析

整个三角形的数字个数是 1+2+...+n = n(n+1)/2，读入和递推各需要遍历一遍，所以时间复杂度和空间复杂度都是 O(n²)。n 最大 1000，n² 为 100 万，时间在毫秒级，内存约 4MB，完全满足题目要求。