因为向左下走的次数与向右下走的次数相差不能超过 1
所以是一左一右或者是一右一左的往下走。
假设三角形行数为 N,那么三角形的最后一行的数字总数为 N。当 N 为奇数时,中间的数字下标为 N//2;当 N 为偶数时,中间两个数字的下标分别为 N//2 和 N//2-1。
在这段代码中,if-else 语句的作用是将最后一行的中间数或中间两数的动态规划数组值设置为最后一行对应位置的数字。这是因为在计算动态规划数组时,如果最后一行的中间数没有被设置,而你直接去访问它,会导致 IndexError 错误。所以在这里要对奇偶数行做特殊处理。
INF = float('inf')
N = int(input())
triangle = []
dp = [[0] * N for _ in range(N)]
for _ in range(N):
line = list(map(int, input().split()))
triangle.append(line)
# 下标从零开始的, 奇数情况下 N//2 就是中间了,奇偶数情况则是 N//2 和 N//2 -1
# 将最后一行的除以上3个点外都设为无穷小,避免影响结果
dp[-1] = [-INF]*len(dp[-1])
if((N-1)%2==0):
dp[-1][N//2] = triangle[-1][N//2]
else:
dp[-1][N//2] = triangle[-1][N//2]
dp[-1][N//2-1] = triangle[-1][N//2-1]
for i in reversed(range(N-1)):
for j in range(i+1):
dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j]
print(dp[0][0])