递归 + 记忆化
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int memo[501][501];
int dfs(int x, int y, vector<vector<int>> &vec) {
if (x == (int)vec.size() - 1) {
return vec[x][y];
}
if (memo[x][y] != -1) {
return memo[x][y];
}
memo[x][y] = max(dfs(x + 1, y, vec), dfs(x + 1, y + 1, vec)) + vec[x][y];
return memo[x][y];
}
int solve(vector<vector<int>> &vec) {
return dfs(0, 0, vec);
}
int main() {
memset(memo, -1 , sizeof(memo));
int n;
cin >> n;
vector<vector<int>> vec;
for (int i = 0; i < n; ++i) {
vector<int> tmp;
for (int j = 0; j <= i; ++j) {
int val;
cin >> val;
tmp.emplace_back(val);
}
vec.emplace_back(tmp);
}
cout << solve(vec) << endl;
return 0;
}