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

#include <bits/stdc++.h>

using namespace std;

const int N = 510;
int a[N][N];
int n;

/**
 深度优先搜索关键点：

 1、递归出口
 本题是超出n行，来到了第n+1行，就意味着搜索结束，可以统计答案了

 2、每一个位置，面临两种选择，分别是正下方和右下方，需要计算它们每一条路线的总和，
 sum(left,right,a[x][y])

 3、需要使用int返回，因为从每个坐标出发，最终都需要返回一个sum和，而这个sum对于调用者
 是有用的,不用采用全局变量，只能用返回int形式。

 4、向下传递，用参数；向上传递，用返回值
 */
int dfs(int x, int y) {
    if (x == n + 1) return 0; // 你们不要指望我了，我是0，你们该咋办就咋办吧~
    if (y > x) return 0;
    return max(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[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;
}