定义 $dp[i][j]$ 表示移动到 $(i,\ j)$ 处的最大收益,考虑状态转移
$$ dp[i][j] = max(dp[i - 1][j],\ dp[i - 1][j - 1]) + a[i][j] $$
利用滚动数组可以优化掉第一维空间,相应的,第二层循环需要倒序,代码如下
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 500;
int n;
int a[N + 7][N + 7], dp[N + 7];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
scanf("%d", &a[i][j]);
memset(dp, -inf, sizeof(dp));
dp[1] = a[1][1];
for(int i = 2; i <= n; ++i)
for(int j = i; j >= 1; --j)
dp[j] = max(dp[j], dp[j - 1]) + a[i][j];
int ans = -inf;
for(int i = 1; i <= n; ++i)
ans = max(ans, dp[i]);
printf("%d\n", ans);
return 0;
}