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: 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.