'''
题目描述 Description
下图给出了一个数字三角形，请编写一个程序，计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。
(1)每一步可沿左斜线向下或右斜线向下
(2)1 < 三角形行数 < 100
(3)三角形数字为0，1，…99
输入描述 Input Description
有很多个测试案例，对于每一个测试案例， 通过键盘逐行输入，第1行是输入整数(如果该整数是0,就表示结束，不需要再处理)，表示三角形行数n，然后是n行数
输出描述 Output Description
输出最大值。
样例输入 Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 Sample Output
30
'''
'''
思路：使用动态规划，构建二维数组dp
dp数组中的数值表示到达当前节点的累计最大值，运用动态规划解决的问题必须是希望在每个子问题上获得最优解(称为最优子结构)
'''
row=int(input())
if row==0:
print(0)
else:
dp=[[0 for i in range(row+1)] for j in range(row+1)]
# python中创建二维列表
for i in range(row):
line=input().split()
for j in range(i+1):
dp[i+1][j+1]=int(line[j])
# print(dp)
for k in range(2,row+1):
for p in range(1,k+1):
dp[k][p]=max(dp[k-1][p-1],dp[k-1][p])+dp[k][p]
last=dp[-1]
max=-1
for elem in last:
if elem>max:
max=elem
print(max)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
