my short python solution


  • 0
    G
    • O(mn) in time & space:
    class Solution(object):
        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            m, n = len(grid), len(grid[0])
            dp = [[sys.maxint]*(n+1) for _ in range(m+1)]
            dp[0][1] = 0
            for i in range(1, m+1):
                for j in range(1, n+1):
                    dp[i][j] = grid[i-1][j-1] + min(dp[i][j-1], dp[i-1][j])
            return dp[-1][-1]
    
    • O(mn) in time, O(n) in space:
    class Solution(object):
        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            m, n = len(grid), len(grid[0])
            dp = [sys.maxint] * (n+1)  # dp[i] means min path sum for previous row to col i-1
            dp[1] = 0
            for i in range(1, m+1):
                dp[1] += grid[i-1][0]
                for j in range(2, n+1):
                    dp[j] = grid[i-1][j-1] + min(dp[j-1], dp[j])
            return dp[-1]
    

Log in to reply
 

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