U400346 欧拉计划第18题 最大路径和 I

从如下数字三角形的顶端出发，不断移动到下一行与其相邻的数直至到达底部，所能得到的最大路径和是 $23$。 $$ \begin{matrix} \color{red}3\color{#333}\\ \color{red}7\color{#333}\quad 4\\ 2\quad \color{red}4\color{#333}\quad 6\\ 8\quad 5\quad \color{red}9\color{#333}\quad 3 \end{matrix} $$ 如上图，最大路径和为 $3+7+4+9=23$。\ 从如下数字三角形的顶端出发到达底部，求所能得到的最大路径和。 $$ \begin{matrix} 75\\ 95\quad 64\\ 17\quad 47\quad 82\\ 18\quad 35\quad 87\quad 10\\ 20\quad 4\quad 82\quad 47\quad 65\\ 19\quad 1\quad 23\quad 75\quad 3\quad 34\\ 88\quad 2\quad 77\quad 73\quad 7\quad 63\quad 67\\ 99\quad 65\quad 4\quad 28\quad 6\quad 16\quad 70\quad 92\\ 41\quad 41\quad 26\quad 56\quad 83\quad 40\quad 80\quad 70\quad 33\\ 41\quad 48\quad 72\quad 33\quad 47\quad 32\quad 37\quad 16\quad 94\quad 29\\ 53\quad 71\quad 44\quad 65\quad 25\quad 43\quad 91\quad 52\quad 97\quad 51\quad 14\\ 70\quad 11\quad 33\quad 28\quad 77\quad 73\quad 17\quad 78\quad 39\quad 68\quad 17\quad 57\\ 91\quad 71\quad 52\quad 38\quad 17\quad 14\quad 91\quad 43\quad 58\quad 50\quad 27\quad 29\quad 48\\ 63\quad 66\quad 4\quad 68\quad 89\quad 53\quad 67\quad 30\quad 73\quad 16\quad 69\quad 87\quad 40\quad 31\\ 4\quad 62\quad 98\quad 27\quad 23\quad 9\quad 70\quad 98\quad 73\quad 93\quad 38\quad 53\quad 60\quad 4\quad 23 \end{matrix} $$ **注意**： 在这个问题中，由于只有 $16384$ 条路径，通过穷举所有的路径来解决问题是可行的。然而，对于[第67题](U438812)，虽然是一道相同类型的题目，但是其中的数字三角形将拥有一百行，就不再能够通过暴力枚举的方法来解决，而需要一个更加聪明的办法！;o)

无。

一个数字，表示所求的答案。