short and sweet Python solution, in-place, DP, AC 85ms

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

Log in to reply

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