Minimum Path Sum

Problem: Minimum Path Sum

Minimum path sum at a certain position is decided by its upper point and left point.

Code in Python:

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

        for i in xrange(1, len(grid[0])):
            grid[0][i] += grid[0][i-1]

        for i in xrange(1, len(grid)):
            for j in xrange(1, len(grid[0])):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])

        return grid[-1][-1]