从如下数字三角形的顶端出发，不断移动到下一行与其相邻的数直至到达底部，所能得到的最大路径和是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$。从如下数字三角形的顶端出发到达底部，求所能得到的最大路径和。

75

95 64

17 47 82

18 35 87 10

20 04 82 47 65

19 01 23 75 03 34

88 02 77 73 07 63 67

99 65 04 28 06 16 70 92

41 41 26 56 83 40 80 70 33

41 48 72 33 47 32 37 16 94 29

53 71 44 65 25 43 91 52 97 51 14

70 11 33 28 77 73 17 78 39 68 17 57

91 71 52 38 17 14 91 43 58 50 27 29 48

63 66 04 68 89 53 67 30 73 16 69 87 40 31

04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注意：本题中总共只有16384条路径，因此穷举也并无不可，不过同样类型的第67题中的数字三角形有一百行，就不再能够通过暴力枚举，而需要更高效的方法来解决。

本题难度:

解答

这是一个典型的动态规划问题，我们用$a(i,j)$表示该三角形中第i行第j列元素，再用$d(i,j)$表示从顶点到第i行第j列元素的最大路径和，那么显然对每行第一列和最后一列的元素而言，路径只有一条，对其他元素则有 $$d(i,j)=\max\{d(i-1,j-1),d(i-1,j)\}+a(i,j)$$ 递推并取最后一行的最大值即得结果 $1074$。

T=[[...]] #将三角形保存在二维列表中，数据太长，此处略去  

maxPath=[[75]]

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

print max(maxPath[-1])