---

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{aligned}
&{\color{red}3}\\
{\color{red}7}&\ \ 4\\
2\ \ &{\color{red}4}\ \ 6\\
8\ \ 5&\ \ {\color{red}9}\ \ 3\\
\end{aligned}
$$

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)

---

最大路径和 II

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

$$
\begin{aligned}
&{\color{red}3}\\
{\color{red}7}&\ \ 4\\
2\ \ &{\color{red}4}\ \ 6\\
8\ \ 5&\ \ {\color{red}9}\ \ 3\\
\end{aligned}
$$

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

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

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

---