Leetcode 64: Minimum Path Sum

 

Code

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid: return 0
        
        m, n = len(grid), len(grid[0])
        # use 1D array as cache, initialized as 
        # the accumulated sum of first line
        dp = list(grid[0])
        for i in xrange(1, n):
            dp[i] += dp[i-1]
        
        for i in xrange(1, m):
            dp[0] += grid[i][0] 
            for j in xrange(1, n):
                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
        
        return dp[-1]

 

Idea 

Use DP to solve this problem.If dp is a m*n 2D array, then `dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]`. As usual, the problem is in 2D but we only need to maintain a 1D cache, dp. When you scan each line of grid, dp actually represents the minimum path sum ending at each element of that line. 

 

Reference: https://discuss.leetcode.com/topic/15269/10-lines-28ms-o-n-space-dp-solution-in-c-with-explanations/2