0%

Problem 67


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.

**3** **7** 4 2 **4** 6 8 5 **9** 3

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 299 altogether! If you could check one trillion (1012) 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。

**3** **7** 4 2 **4** 6 8 5 **9** 3

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

在这个15K的文本文件triangle.txt(右击并选择“目标另存为……”)中包含了一个一百行的三角形,求从其顶端出发到达底部,所能够得到的最大路径和。

注意:这是第18题的强化版。由于总路径一共有299条,穷举每条路经来解决这个问题是不可能的!即使你每秒钟能够检查一万亿(1012)条路径,全部检查完也需要两千万年。存在一个非常高效的算法能解决这个问题。;o)