My python solution . using recursively. Is there any short and easy solution?


  • 0
    D
    class Solution:
        def minPathSum(self, grid):
            sumMap = {}
            def pathSum(rows,cols):
                if (rows,cols) in sumMap:
                    return sumMap[(rows, cols)]
                else:
                    sum = 0
                    flag = 0
                    if rows == 1:
                        for x in xrange(cols):
                            sum += grid[rows-1][x]
                            flag = 1
                    elif cols == 1 and flag != 1:
                        for x in xrange(rows):
                            sum += grid[x][cols-1]
                    else:
                        sum = min(pathSum(rows-1, cols)+grid[rows-1][cols-1], pathSum(rows, cols-1) + grid[rows-1][cols-1])
                    sumMap[(rows,cols)] = sum
                    return sum 
            return pathSum(len(grid), len(grid[0]))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.