说明

数字三角形第 1 行 1 个数，第 2 行 2 个数...第 n 行 n 个数。从顶部出发，每次只能向左下或右下走到底部，求路径上数字的**最大和**。

输入格式

第一行，整数 n（1 \le n \le 100）。 接下来 n 行，第 i 行有 i 个数（值范围 [0, 100]）。

输出格式

一行，最大路径和。

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

提示

自底向上递推： dp[i][j] = a[i][j] + \max(dp[i+1][j], dp[i+1][j+1]) n = int(input()) a = [list(map(int, input().split())) for _ in range(n)] dp = a[-1][:] # 最后一行的值 for i in range(n-2, -1, -1): for j in range(i+1): dp[j] = a[i][j] + max(dp[j], dp[j+1]) print(dp[0]) 自底向上，最终 dp[0] 即答案，无需二维数组。