从上到下DP

#include <iostream>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
    cin>>n;

    for (int i = 1; i <= n;i ++ ) 
        for(int j = 1; j <= i;j ++ )
            cin >> a[i][j];

    for (int i = 1;i <= n;i ++ )
        for(int j = 0;j <= i + 1; j ++ )   // 多初始化边界
            f[i][j] = -INF;

    f[1][1] = a[1][1];

    for (int i = 2; i <= n;i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    cout << res << endl;

    return 0;
}

从下到上DP

#include <iostream>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
    cin >> n;
    for(int i =1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin >> a[i][j];

    for(int i =1;i<=n;i++)
        for(int j=1;j<=i;j++)
            if(i==n) f[i][j] = a[i][j];   // 初始化
            else f[i][j]=-INF;

    for(int i=n-1;i>=1;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j],f[i+1][j+1]) + a[i][j];

    cout<<f[1][1]<<endl;

    return 0;


}