DFS 记忆化搜索

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

#define DBG(x) cout << #x << "=" << x << endl

const int N = 1005;
int n, a[N][N], f[N][N];

int dfs(int x, int y) {
  // 查缓存，记忆化
  if (f[x][y] != -1)
    return f[x][y];
  // 边界：最后一行
  if (x == n)
    return f[x][y] = a[x][y];
  // 记忆化搜索
  return f[x][y] = max(dfs(x + 1,y), dfs(x + 1, y + 1)) + a[x][y];
}

void solve() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= i; j++)
      scanf("%d", &a[i][j]);

  memset(f, -1, sizeof f);
  dfs(1, 1);
  printf("%d\n", f[1][1]);
}

int main() {
  solve();

  return 0;
}