---

Problem 67

---

Maximum Path Sum II

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is $23$.

$$\begin{array}{rl}& 3\\ 7& 4\\ 2& 46\\ 85& 93\end{array}$$

That is, $3+7+4+9=23$.

Find the maximum total from top to bottom in triangle.txt(right click and ‘Save Link/Target As…’), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are $2^{99}$ altogether! If you could check one trillion (${10}^{12}$) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

---

最大路径和（二）

从下面展示的三角形的顶端出发，不断移动到在下一行与其相邻的元素，能够得到的最大路径和是$23$。

$$\begin{array}{rl}& 3\\ 7& 4\\ 2& 46\\ 85& 93\end{array}$$

如上图，最大路径和为$3+7+4+9=23$。

在文本文件[triangle.txt] (https://projecteuler.net/project/resources/p067_triangle.txt)中包含了一个一百行的三角形，求从其顶端出发到达底部，所能够得到的最大路径和。

注意：这是第18题的强化版。由于总路径一共有$2^{99}$条，穷举每条路经来解决这个问题是不可能的！即使你每秒钟能够检查一万亿（${10}^{12}$）条路径，全部检查完也需要两千万年。存在一个非常高效的算法能解决这个问题。;o)

---