文字教学

这道题是经典的动态规划问题，核心思路是从下往上递推，避免重复计算：

1. 状态定义：直接在原数组上更新，a[i][j] 表示从第 i 行第 j 列走到底部的最大路径和。
2. 状态转移：从倒数第二行开始往上遍历，每个位置的最大路径和 = 当前数字 + 下一行左右两个位置的最大值，即 a[i][j] += max(a[i+1][j], a[i+1][j+1])。
3. 结果：递推到顶部后，a[1][1] 就是从最高点到底部的最大路径和。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int a[N][N];

int main() {
    int r;
    cin >> r;
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> a[i][j];
        }
    }
    // 从下往上递推
    for (int i = r-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;
}