python/TangDou/AcWing/LineDP/898_ZhengXu_ErWei.cpp

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

const int N = 510;
const int INF = 0x3f3f3f3f;
int f[N][N];
int a[N][N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];

    memset(f, -0x3f, sizeof f); // 预求最大，先设最小
    // 其实自上而下版本之所以需要初始化-INF，是因为每个枚举到的位置需要从它头顶和它的左上侧取值对比
    // 而它的正上方可能是不存在的，如果不初始化，就是0
    // 本题数据还可能是负数，就会造成它可会从正上方取来一个0做为最大值，造成结果错误
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    int res = -INF;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}