Maximum Path Sum II

Since we took the time to find an efficient method in problem 18, we can just reuse that method here.

So just read the triangle into a list-of-lists.

with open("txt/0067_triangle.txt") as f:
    triangle = [[int(n) for n in line.split(' ')] for line in f]

Then we'll use the bottom-up method from before (you could also use the top-down method).

def max_path_sum(tri):
    for i in reversed(range(0, len(tri) - 1)):
        for j in range(0, len(tri[i])):
            tri[i][j] += max(tri[i+1][j], tri[i+1][j+1])
            
    return tri[0][0]

max_path_sum(triangle)

7273

Copyright (C) 2025 filifa

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.