算法 O(n^2)

利用两行数组来模拟，记录从上而来，到当前位置的累计最大值。
最后，扫描一遍数组即可。

c++

#include<iostream>
#include<algorithm>
using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)

int n;
const int INF=5000005;
int a[2][505];

int main(){

    cin>>n;
    ffor(i,0,n+1){
        a[0][i]=a[1][i]=-INF;
    }
    cin>>a[0][1];

    int now=1,pre=0;

    ffor(i,2,n+1){//控制行数
        ffor(j,1,i+1){//该行的个数
            int x;cin>>x;
            a[now][j]=max(a[pre][j-1],a[pre][j])+x;//从头顶两个选出个较大的加上当前值
        }
        swap(now,pre);//滚动当前行
    }

    int ans=-INF;
    ffor(i,0,n+1) ans=max(ans,a[pre][i]);

    cout<<ans<<endl;

    return 0;
}