从如下数字三角形的顶端出发，不断移动到下一行与其相邻的数直至到达底部，所能得到的最大路径和是23。

\begin{align*} &{\color{red}3}\\ {\color{red}7}&\ \ 4\\ 2\ \ &{\color{red}4}\ \ 6\\ 8\ \ 5&\ \ {\color{red}9}\ \ 3\\ \end{align*} 如上图，最大路径和为$3 + 7 + 4 + 9 = 23$。

文件triangle.txt中是一个一百行的三角形，求从其顶端出发到达底部所能得到的最大路径和。

本题难度:

解答

与第18题的做法完全相同，结果是$7273$。

T=[]
with open("067_triangle.txt") as f:
    for line in f:
        T.append([int(i) for i in line.split()])

maxPath=[[59]]
for row in T[1:]:
    maxPath.append([maxPath[-1][0]+row[0]]+[val+max(maxPath[-1][col],maxPath[-1][col+1]) for col,val in enumerate(row[1:-1])]+[row[-1]+maxPath[-1][-1]])
print max(maxPath[-1])