顺序：从第一层走到最后一层

逆序：从最后一层走到第一层

只有顺序的边界需要初始化

顺序边界要-INF,不带备份数组的逆序的边界可以不用初始化，

带备份数组的要初始化为0，相当于不用初始化

顺序的结果要遍历最后一层取最大值

而逆序只要取第一层的数就ok，因为第一层只有一个数

顺序的超短版本（时间最快）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n, f[N][N];

int main()
{
    cin >> n;
    int res = -INF;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
        {
            if (j == 1) f[i][0] = f[i][i + 1] = -INF;//初始化
            scanf("%d", &f[i][j]);//读入数据                  
            if (i > 1) f[i][j] = f[i][j] + max(f[i - 1][j], f[i - 1][j - 1]); //状态计算
            if (i == n) res = max(res, f[i][j]);//遍历第n层
        }
    cout << res << endl;
}

顺序一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n, f[N], a;

int main()
{
    //读入数据
    cin >> n;
    int res = -INF;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j >= 1; j -- )
        {
            f[0] = f[i + 1] = -INF;
            scanf("%d", &a);
            if (i == 1) f[1] = a;
            if (i >  1) f[j] = a + max(f[j], f[j - 1]); //状态计算
            if (i == n) res = max(res, f[j]);//遍历第n层
        }
    cout << res << endl;
}

逆序（不带备份数组）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n;
int f[N][N];//初始化
int a[N][N];//若要a数组则需要从第n层开始

int main()
{
    //读入数据
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &f[i][j]);
    //状态计算,由左下和右下得来
    for (int i = n - 1; i >= 1; i -- )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = f[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);

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

朴素顺序(带备份数组)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

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

int main()
{
    //读入数据
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);
    //初始化
    f[1][1] = a[1][1];
    for (int i = 1; i < n; i ++ )
            f[i][0] = f[i][i + 1] = -INF;

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

    //遍历第n层
    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    cout << res << endl;
}

朴素顺序（不带备份数组）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

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

int main()
{
    //读入数据
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &f[i][j]);
    //初始化
    for (int i = 1; i < n; i ++ )
            f[i][0] = f[i][i + 1] = -INF;

    //状态计算
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = f[i][j] + max(f[i - 1][j], f[i - 1][j - 1]);

    //遍历第n层
    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    cout << res << endl;
}

逆序（带备份数组）可以发现，区别不大

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int f[N][N];//初始化
int a[N][N];

int main()
{
    //读入数据
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);
    //状态计算,由左下和右下得来
    for (int i = n; i >= 1; i -- )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);

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