AcWing 3304. 数字三角形
原题链接
简单
作者:
跂未
,
2024-03-25 21:22:19
,
所有人可见
,
阅读 6
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])