[数据结构与算法]064.minimum-path-sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0
        dp = [0 for _ in xrange(0, len(grid[0]))]
        dp[0] = grid[0][0]
        
        for j in xrange(1, len(grid[0])):
            dp[j] = dp[j - 1] + grid[0][j]
            
        for i in xrange(1, len(grid)):
            pre = dp[0] + grid[i][0]
            for j in xrange(1, len(grid[0])):
                dp[j] = min(dp[j], pre) + grid[i][j]
                pre = dp[j]
            dp[0] += grid[i][0]
        
        return dp[-1]