C++ 代码
裸dp
#include <iostream>
#include <cstring>
const int MAXN = 500+5;
using namespace std;
int t[MAXN][MAXN], dp[MAXN][MAXN] = {0};
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
scanf("%d", &t[i][j]);
}
}
dp[0][0] = t[0][0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = dp[i-1][j] + t[i][j];
} else if (j == i) {
dp[i][j] = dp[i-1][j-1] + t[i][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + t[i][j];
}
}
}
int ans = -0x3fffffff;
for (int i = 0; i < n; i++)
ans = max(ans, dp[n-1][i]);
printf("%d\n", ans);
return 0;
}