Maximum path sum of triangle of numbers

Question

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[1], 'r') as f:
        triangle = f.readlines()

    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.

Answer 1

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.