dp,f[i][j]表示第i行第j的位置的最大路径和。这个题要求:向左下走的次数与向右下走的次数相差不能超过 1,
模拟几次发现从上到下符合这个要求的路径终点在最后一层的中间位置
import sys
inf = -sys.maxsize
n = int(input())
N = 510
mp = []
for _ in range(n):
mp.append(list(map(int,input().split())))
f = [[inf]*N for _ in range(N)]
f[0][0] = mp[0][0]
for i in range(1,n):
for j in range(i+1):
if j-1>=0 and j<=i-1:
f[i][j] = mp[i][j] + max(f[i-1][j-1],f[i-1][j])
elif j-1<0:
f[i][j] = mp[i][j] + f[i-1][j]
elif j>i-1:
f[i][j] = mp[i][j] + f[i-1][j-1]
print(max(f[n-1]))