Maximum Path Sum I

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.
37 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

This problem is an example of a dynamic programming problem, a relatively advanced Computer Science concept. In this problem, you can’t simply choose the largest number on each row, because the choice of the largest number on one row might interfere with the ability to pick a larger number on a row after the next.

We can start by creating an array to store the maximum sum for each position. Initially, our array contains only one element, which is the number at the top of the triangle (75).

After that, for each row in the triangle, we add to our array two elements:

one for the case where we move ‘left’ (the current element’s value plus the value to its left on the row below) and one for the case where we move ‘right’ (the current element’s value plus the value to its right on the row below).

We continue this process for each row, eventually resulting in an array where each element represents the maximum total sum that can be achieved by moving to that position.

Then, we iterate through the array and find the maximum value, which gives us the maximum total from top to bottom of the triangle. But it’s easier to start from the bottom of the pyramid and work our way upwards.

The idea is to start at the second to last row and for each number in that row, add the maximum of the two numbers below it from the row beneath.

Replace the current number with that sum. By doing this, you are effectively eliminating the bottom row while keeping the maximum path sum information in the current row.

Then move up a row and repeat until you get to the top. The number at the top will be the maximum path sum.

Here is a python implementation for the problem,

“`python
triangle = [
[75],
[95, 64],
[17, 47, 82],
[18, 35, 87, 10],
[20, 04, 82, 47, 65],
[19, 01, 23, 75, 03, 34],
[88, 02, 77, 73, 07, 63, 67],
[99, 65, 04, 28, 06, 16, 70, 92],
[41, 41, 26, 56, 83, 40, 80, 70, 33],
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
[63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
[04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23]
]

for row in range(len(triangle)-2, -1, -1):
for col in range(len(triangle[row])):
triangle[row][col] += max(triangle[row+1][col], triangle[row+1][col+1])

print(triangle[0][0]) # Output: 1074
“`

This is a more computationally efficient solution that does not involve enumerating all possible paths.

More Answers: