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

#include <bits/stdc++.h>

using namespace std;
const int N = 510;
int a[N][N];
int f[N][N]; // 记录以(x,y)坐标位置为根的子树的路径最大和
int n;

int dfs(int x, int y) {
    if (f[x][y]) return f[x][y]; // 如果算过，就直接返回
    if (x == n + 1) return 0;    // 你们不要指望我了，我是0，你们该咋办就咋办吧~
    if (y > x) return 0;
    // 算过的都记录下来，别丢掉,左下方，x+1,y,右下方，x+1,y+1
    f[x + 1][y] = dfs(x + 1, y);
    f[x + 1][y + 1] = dfs(x + 1, y + 1);
    f[x][y] = max(f[x + 1][y], f[x + 1][y + 1]) + a[x][y];
    return f[x][y];
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    int res = dfs(1, 1);
    printf("%d", res);
    return 0;
}