Project Euler #82 - path sum: three ways Project Euler problem 82 asks:



Here's my solution:

def main():    
    matrix = [
        [131, 673, 234, 103,  18],
        [201,  96, 342, 965, 150],
        [630, 803, 746, 422, 111],
        [537, 699, 497, 121, 956],
        [805, 732, 524,  37, 331]
    ]

    size = len(matrix)
    best = [matrix[row][0] for row in range(size)]

    for col in range(1, size):
        column = [matrix[row][col] for row in range(size)]
        tmp = column[:]

        for i in range(size):
            column[i] += best[i] # right

            for j in range(0, i): # up
                if sum([best[j]]+tmp[j:i+1]) &lt; column[i]:
                    column[i] = sum([best[j]]+tmp[j:i+1])

            for k in range(i, size): # bottom
                if sum([best[k]] +tmp[i:k+1]) &lt; column[i]:
                    column[i] = sum([best[k]] +tmp[i:k+1])

        best = column
        #print(best)

    return min(best)


if __name__ == "__main__":
    print(main())


Please advise how it can be improved.
To solve the Project Euler challenge, you'll have to handle a large matrix from a file.  Therefore, your function should accept the matrix as a parameter.

You used size to represent both the number of rows and the number of columns.  I would use two variables to avoid hard-coding the assumption that the input is a square matrix.

Your dynamic programming algorithm is sound.  I would use the min() function to avoid finding the minimum by iteration.  Also, setting best all at once instead of mutating the elements of column avoids having to copy column into a temporary variable.

def euler82(matrix):
    nrows, ncols = len(matrix), len(matrix[0])
    best = [matrix[row][0] for row in range(nrows)]

    for col in range(1, ncols):
        column = [matrix[row][col] for row in range(nrows)]

        best = [
            # The cost of each cell, plus...
            column[row] +

            # the cost of the cheapest approach to it
            min([
                best[prev_row] + sum(column[prev_row:row:(1 if prev_row &lt;= row else -1)])
                for prev_row in range(nrows)
            ])
            for row in range(nrows)
        ]

        #print(best)

    return min(best)