法1 自上而下的dp

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110,INF = 100000000;
int f[N][N];
int a[N][N];


int main(){

    int n;
    cin >> n;

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

    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]+a[i][j],f[i-1][j-1]+a[i][j]);
        }
    }

    /*
    for(int i = 1;i <= n;i++){
        cout << f[n][i] << endl;
    }
    */

    if(n % 2 == 1)cout << f[n][n/2+1] << endl;//n是奇数时，一定会走到中间那个数
    else{
        cout << max(f[n][(n)/2],f[n][(n)/2+1]);//n是偶数时，会走到中间两个数
    }

    return 0;
}

注意这里的k那一维表示的含义与上面第二维的含义不同，k表示向左走了多少步，而上面表示走到哪里
走的步数要（n-1）/2判断
法2 自下而上的dp

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 110;

int f[N][N][N];
int a[N][N];
int 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++)f[n][i][0] = a[n][i];

    //f[i][j][k]----->表示到i，j，向左下走k次。
    for(int i = n-1;i >= 1;i--){
        for(int j = 1;j <= i;j++){
            for(int k = 0;k <= n-i;k++){
                f[i][j][k] = f[i+1][j+1][k]+a[i][j];//从右下来的，则左下走k次，k与下一层是一样的
                if(k >= 1){//当下一层的往左下的次数是大于1，此时才可能是从左下来的，因为要减去1
                    f[i][j][k] = max(f[i][j][k],f[i+1][j][k-1] + a[i][j]);
                }
            }
        }
    }

    if(n % 2 == 1){//n是奇数，则移动次数n-1位偶数，则一定是对半分的次数
        cout << f[1][1][(n-1)/2];
    }
    else{//n是偶数，移动次数n-1是奇数，则可能是1-0，也可能0-1组合
        cout << max(f[1][1][(n-1)/2],f[1][1][(n-1)/2+1]);
    }

    return 0;
}

dfs

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;

int f[N][N];
int res = -1;
int n;

void dfs(int x,int y,int left,int right,int w){
    if(x == n){
        if(abs(left-right) <= 1)
            res = max(res,w);
        return ;
    }
    dfs(x+1,y,left+1,right,w+f[x+1][y]);
    dfs(x+1,y+1,left,right+1,w+f[x+1][y+1]);
}

int main(){

    cin >> n;

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

    dfs(1,1,0,0,f[1][1]);
    cout << res << endl;

    return 0;
}