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 3That 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 23NOTE: 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)
We can start at the top of the triangle and take a greedy approach where we try to construct a path with the maximum sum by always picking the larger of the two adjacent numbers below. But this way we might miss out on a much larger sum further down some other path. So the greedy approach is locally optimal but not globally optimal since we can't see the consequences of our choices until we've reached the bottom.
Instead we want to take a dynamic programming approach and consider the right subproblem. If we define the subproblem as "what is the maximum path sum starting from this position and going down?" then we can solve it bottom-up. Starting at the bottom of the triangle, for each position we will compute the maximum path sum obtainable by going downwards from that position.
There is nowhere to go downwards if you start anywhere in the bottom row, so we don't have to do anything there. For the second row from the bottom, the maximum path sum will be the number at that location plus the larger of the two numbers below it. We can repeat this for the third row from the bottom and so on. By the time we get to the very top we will have the maximum path sum over the entire triangle in the very top element.
const TRIANGLE = [
[75],
[95, 64],
[17, 47, 82],
[18, 35, 87, 10],
[20, 4, 82, 47, 65],
[19, 1, 23, 75, 3, 34],
[88, 2, 77, 73, 7, 63, 67],
[99, 65, 4, 28, 6, 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, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
]
function max_path_sum(triangle)
max_sums = deepcopy(triangle)
# Start from the second-to-last row and work upwards
for i in (length(max_sums) - 1):-1:1
for j in 1:length(max_sums[i])
# Add the maximum of the two adjacent values in the row below
max_sums[i][j] += max(max_sums[i + 1][j], max_sums[i + 1][j + 1])
end
end
return max_sums[1][1]
end
This computes the solution in 2.415 μs.