# Maximum path sum of triangle of numbers

I have implemented the maximum path sum of a triangle of integers (problem 18 in project euler) and I am wondering how I can improve my solution. My solution is below:

def problem18(triangle, height):
return dp_triangle(triangle, height, 0, 0, dict())

def dp_triangle(triangle, height, row, col, maxs):
if row == height - 1:
return int(triangle[row][col])

keyLeft = str(row + 1) + "," + str(col)
keyRight = str(row + 1) + "," + str(col + 1)

if keyLeft in maxs:
maxLeft = maxs[keyLeft]
else:
maxLeft = dp_triangle(triangle, height, row + 1, col, maxs)
maxs[keyLeft] = maxLeft

if keyRight in maxs:
maxRight = maxs[keyRight]
else:
maxRight = dp_triangle(triangle, height, row + 1, col + 1, maxs)
maxs[keyRight] = maxRight

return max(maxLeft, maxRight) + int(triangle[row][col])


To call this function I have the following:

def main(argv):
with open(argv, 'r') as f:

height = len(triangle)

triangle = [x.strip().split() for x in triangle]

print(problem18(triangle, height))


I just pass a text file with the triangle of numbers to the program. These numbers are separated by whitespace.

• Do you have an example of how you call this function. It would mean reviews don't have to guess how to use your function and just improve the code. – Peilonrayz Feb 22 '17 at 15:36
• Thanks for the input. I just added an input with a main() function showing how I call it. Please let me know if you need any more information. For reference, a sample data set can be found here: projecteuler.net/problem=18 – Robert Grossman Feb 22 '17 at 16:10
• This problem is a classic example of dynamic programming. Try taking a look at Dreamshire – Tomáš Král Feb 26 '17 at 17:06

dp_triangle(triangle, height, row, col) depends on three things: dp_triangle(triangle, height, row + 1, col), dp_triangle(triangle, height, row + 1, col + 1), and triangle[row][col]. Therefore it's not necessary to cache more than one row at a time. With that insight you should be able to refactor it to not need dict() at all.
I actually prefer to solve this problem by going down rather than up. That is to say, I define my intermediate result as v(row, col) = max(v(row-1, col-1), v(row-1, col)) + triangle[row][col]. Then the double-array of triangle can be processed in order using a simple for loop, as opposed to in reverse using a slightly more complicated for loop.