dp ：

（剪枝：若当前点离中心点的偏移量减剩下的行数大于1，则跳过）

C++ 代码

#include<iostream>
using namespace std;
int a[101][101];
int dp[101][101];
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++){
        for(int j=1; j<=i; j++){
            if( abs( j - i/2 )- n + i > 1)continue;
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + a[i][j];
        }
    }
    if(n%2==1)cout << dp[n][n/2+1]; //n为奇数必走回中心点
    else cout << max( dp[n][n/2], dp[n][n/2+1] );  //n为偶数有两种情况
    return 0;
}

dfs ：

用一样的思路n=30就超时了555

C++ 代码

#include<iostream>
using namespace std;
int a[101][101];
int n,ans=0;

void dfs(int i,int j,int sum,int dir){
    if( abs(dir) - n + i > 1)return;
    if(i == n) {
        if(dir==1 ||dir==-1 ||dir==0 )ans = max(ans,sum);
        return;
    }
    dfs(i+1, j+1, sum+a[i+1][j+1], dir+1 );
    dfs(i+1, j, sum+a[i+1][j], dir-1);
}

int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++)cin>>a[i][j];
    }
    dfs(1,1,a[1][1],0);
    cout << ans;
    return 0;
}