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;
}