解题思路

数塔问题：从上往下走，每一步只能走到下一层相邻的两个数，求经过的数字之和最大是多少。

这是一个经典的动态规划问题。

思路：从下往上推。

到某个位置 (i,j) 时，下一步只能走到 (i+1,j) 或 (i+1,j+1)。所以倒过来想：

第 i 行第 j 个位置的最大和 = 自己 + 下一层相邻两个位置（dp[i+1][j] 和 dp[i+1][j+1]）中更大的那个。

步骤：

1. 读入数塔
2. 从倒数第二层开始，往上逐层计算：
   • 每个位置的最大和 = 自己 + max(下面左, 下面右)
3. 算到最顶层，a[1][1] 就是整个数塔的最大和

为什么从下往上？ 因为上层的值依赖下层的值，从下往上算，用到下层时它的值已经算好了。

举例：

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

从底往上算，最优路径是 7→3→8→7→5，和 = 30。

参考代码

#include <iostream>
using namespace std;

int a[110][110];

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++) {
            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];  // 顶层就是最大和
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，每个位置算一次
• 空间复杂度：O(N²)，二维数组存数塔