Project Euler Problem 67 Solution: Maximum path sum II

Project Euler Problem 67 Statement

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 5
           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, 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⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it.

Solution

To solve this problem and problem 18, which is much smaller, start the search from the bottom to the top, adding the maximums along the way. This will “bubble” the maximum path total to the top of the triangle.

Let’s follow this technique, step–by–step, with the 4 row triangle example above to show how this works.

A step–by–step look at this algorithm

Initial array           After the first
                           iteration
      3                        3
     7 5                      7 5
    2 4 6                   10 13 15
   8 5 9 3

Starting at the bottom, take the first pair, 8 and 5, pick the maximum and replace the 2 in the previous row with their sum 8 + 2 = 10.
Take the next pair, 5 and 9, pick the maximum and replace the 4 in the previous row with their sum 9 + 4 = 13.
Finally, take the last pair, 9 and 3, pick the maximum and replace the 6 in the previous row with their sum 9 + 6 = 15.

If you think about it, we simply solved the maximum path from the last row to the second to last row by considering each sub–problem for the following three triangles.

   2      4      6
  8 5    5 9    9 3

Keep that in mind and let’s do it again with our new array.

Take the larger of 10 and 13 and add it to 7 making 13 + 7 = 20.
Take the larger of 13 and 15 and add it to 5 making 15 + 5 = 20.

Now our array looks like:

  3
20 20

At last, we take the larger of 20 and 20 (yes, I know they’re the same) and add it to 3 making 20 + 2 = 23.
And our array looks like:

Which is the maximum total path in the triangle. And if you follow this logic then you just witnessed dynamic programming in action—truly short and simple.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 67

HackerRank Project Euler 67 varies the number of rows in the triangle; 1 ≤ N ≤ 100 and runs 10 test cases

Python Source Code

for _ in range(int(input())):
    N = int(input())
    table = [list(map(int, input().split())) for _ in range(N)]
 
    for row in range(len(table)-1, 0, -1):
        for col in range(0, row):
           table[row-1][col] += max(table[row][col], table[row][col+1])
 
    print(table[0][0])

Project Euler Problem 67 Statement

Solution

A step–by–step look at this algorithm

HackerRank version

Python Source Code

Last Word