三角形最大路径和

解题思路:

注意事项:

参考代码:

def maximumTotal(triangle):
   n = len(triangle)
   dp = [[0] * n for _ in range(n)]
   for i in range(n - 1, -1, -1):
       for j in range(i + 1):
           if i == n - 1:
               dp[i][j] = triangle[i][j]
           else:
               dp[i][j] = triangle[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1])
   return dp[0][0]


T = int(input())
results = []
for _ in range(T):
   N = int(input())
   triangle = []
   for _ in range(N):
       row = list(map(int, input().split()))
       triangle.append(row)
   result = maximumTotal(triangle)
   results.append(result)

for res in results:
   print(res)