Simple python bottom up solution


  • 0
    S
    class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        pre = [0]*len(grid)
        n = len(grid)
        m = len(grid[0])
        pre[-1] = grid[-1][-1]
        for i in range (n-2, -1, -1):
            pre[i] = grid[i][m-1] + pre[i+1]
        for i in range (len(grid[0])-2,-1,-1):
            cur = [0]*len(grid)
            cur[-1] = grid[-1][i]+pre[-1]
            for j in range (len(grid)-2,-1,-1):
                cur[j] = min(cur[j+1], pre[j])+grid[j][i]
            pre=cur[:]
        return pre[0]

Log in to reply
 

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