dp思想 三个点分类讨论

解题思路:

注意事项:

参考代码:

n=int(input())

a=[]

dp=[[0 for _ in range(100)] for _ in range(100)]

for i in range(n):

    a.append(list(map(int,input().split())))

dp[0][0]=a[0][0]

for i in range(1,n):

    for j in range(i+1):

        if(j==0):

            dp[i][j]=dp[i-1][j]+a[i][j]

        if(j==i):

            dp[i][j]=dp[i-1][j-1]+a[i][j]

        else:

            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]

if(n&1==1):

    print(dp[n-1][n//2])

else:

    print(max(dp[n-1][n//2],dp[n-1][n//2-1]))