Dp

   *              *                *
  /              /                  \ 
 *   *          *   *            *   *
  \              \                  / 
*  *  *        *  *  *          *  *  *
                 /                  \
             *  *  *  *        *  *  *  *  

经观察得n为偶数时，最后一层落在的点一定在n/2或n/2+1,而n为奇数时，最后一层落在的点一定在n/2+1
f[i][j]表示所有从头开始往下走到第i层第j个的路径的最大值

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110;
int n;

int f[N][N];
int triangle[N][N];
int main()
{
    scanf("%d",&n);
    for(int i = 1; i<=n; i++)
        for(int j = 1; j <=i; j++)
            scanf("%d",&triangle[i][j]);

    for(int i = 1; i<= n; i++)
        for(int j = 1; j <=i; j++)
            f[i][j] = max(f[i-1][j],f[i-1][j-1]) + triangle[i][j];
    if(n % 2 == 0) printf("%d\n", max(f[n][n/2],f[n][n/2+1]));
    else printf("%d\n", f[n][n/2+1]);
    return 0;
}

dfs+剪枝

超时,过样例5/10,n=50时就不行了

#include<iostream>
using namespace std;
const int N = 1e6+10;

//三角形的坐标   (i+1)i/2+j   (j<=i)
int n;
int triangle[N];
int maxN;
int maxlevel[N];


void dfs(int x, int y, int cnt, int step)
{
    cnt += triangle[(x+1)*x/2+y];
    if(x == n )
    {
        if( abs(step)<=1 ) maxN = max(maxN,cnt);
        return ;
    }

    //剪枝
    if(abs(step)>n-x) return ;  // 再走也无法改变左右步数超过1的事实
    int temp = cnt;
    temp += maxlevel[n-1]-maxlevel[x]; //加上下面每层的最大数也无法超过maxN
    if(temp <= maxN) return;

    if(x == n-1){
        dfs(x+1,y,cnt,step);
        dfs(x+1,y+1,cnt,step);
    }
    else
    {
        dfs(x+1,y,cnt,step-1);
        dfs(x+1,y+1,cnt,step+1);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i<n; i++)
    {
        int temp = 0;
        for(int j = 0; j <=i; j++)
        {
            scanf("%d",&triangle[(i+1)*i/2+j]);
            temp = max(temp,triangle[(i+1)*i/2+j]);
        }
        maxlevel[i] = maxlevel[i-1]+temp;
    }
    dfs(0,0,0,0);
    printf("%d",maxN);
}