# Project Euler Problem 18: Maximum Path Sum I¶

The source code for this problem can be found here.

## Problem 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$$.

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

That is, $$3 + 7 + 4 + 9 = 23$$.

Find the maximum total from top to bottom of the triangle below:

$\begin{split}&&&&&&&&&&&&&&& 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\end{split}$

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)

## Solution Discussion¶

This problem can be efficiently solved using a dynamically programming algorithm.

The algorithm iterates over the rows of the triangle, $$t_i$$, and builds a list of partial solutions, $$p_j$$, that provide the maximum path sum ending at the $$(i,j)^{th}$$ position in the triangle. This is built one row at a time.

Upon reaching the final row, $$p_j$$ contains the maximum path sum from the root of the triangle to $$t_{n - 1,j}$$ for $$j \in 0, \dots, n - 1$$. The maximum path sum overall is simply then the maximum value in $$p$$.

As noted in the problem description, a naive brute-force must consider each of the $$2^{15} = 32768$$ distinct paths. While this would be relatively quick, the algorithm has exponential time complexity in the depth $$n$$ of the triangle. That is, $$O(2^{n-1})$$ where $$n$$ is the number of rows in the triangle.

Note

the problem is wrong, there are actually $$2^{15}$$ paths not $$2^{14}$$ through this triangle.

This dynamic programming algorithm has time complexity $$O(1 + 2 + ... + n) = O(n^2)$$.

## Solution Implementation¶

from typing import List

def max_path_sum(triangle: List[List[int]]) -> int:
""" Compute the maximum path sum through the triangle

A path moves from the triangle root to a leaf node, with one entry from each row. As the path moves from one row to
the next, it may connect to adjacent entries only.

:param triangle: :math:2-dimensional list of integers (the triangle)
:return: the maximum path sum through triangle
"""

# Perform some simple validation on triangle
assert isinstance(triangle, list), "triangle must be a triangular 2-dimensional list of integers"
for i, row in enumerate(triangle):
assert len(row) == i + 1, "row {} has length {}, it should have {} to be triangular".format(i, len(row), i + 1)
for elt in row:
assert isinstance(elt, int), "triangle entries must be integers"

# Build up the answer one row at a time using a dynamic programming algorithm
n = len(triangle)
partial_sum_to = [0] * n
for i in range(n):
# After each iteration i, part_sum_to[j] is the maximum path sum ending at triangle[i][j]
temp_partial_sum = partial_sum_to.copy()  # keep an unmodified version of partial_sum from last iteration
temp_partial_sum[0] = partial_sum_to[0] + triangle[i][0]  # only one possible path ends at triangle[i][0]
for j in range(1, i):
temp_partial_sum[j] = max(partial_sum_to[j - 1], partial_sum_to[j]) + triangle[i][j]
temp_partial_sum[i] = partial_sum_to[i - 1] + triangle[i][i]  # only one possible path ends at triangle[i][i]
partial_sum_to = temp_partial_sum

return max(partial_sum_to)  # find the maximum path sum ending at one of the leaf nodes

def solve():
""" Compute the answer to Project Euler's problem #18 """
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]
]
return max_path_sum(triangle)

Parameters: triangle (List[List[int]]) – $$2$$-dimensional list of integers (the triangle) int the maximum path sum through triangle