算法1

(dp) $O(n(n+1)/2)$

以行为阶段划分,当前行第j列的值跟前一行的j列或者j-1列有关

C++ 代码

#include <iostream>

using namespace std;

const int N = 502;
long long f[N];
int a[N];

int main(){
    int n;
    long long ans = -1e9;
    cin >> n;
    for (int i=0; i<n; i++){
        for (int j=0; j<i+1; j++) cin >> a[j];
        for (int j=i; j>-1; j--) {
            if (j==0) f[j] = f[j] + a[j];
            else if (j==i) f[j] = f[j-1]+a[j];
            else f[j] = max(f[j-1] + a[j], f[j]+a[j]);
            if (i==n-1) ans = max(ans, f[j]);
        }
    }
    cout << ans;
    return 0;
}