MinimumPathSum

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        if n == 0:
            return 0
        if m == 1:
            return sum(grid[0])
        if n == 1:
            return sum([grid[i][0] for i in range(m)])
        return self.allPaths(grid, 0, 0, m, n, [])

    def allPaths(self, grid, y, x, m, n, path):
        newPath = path + [grid[y][x]]
        if y == m-1 and x == n-1:
            return sum(newPath)
        sums = []
        if y < m-1:
            sums.append(self.allPaths(grid, y+1, x, m, n, newPath))
        if x < n-1:
            sums.append(self.allPaths(grid, y, x+1, m, n, newPath))

        return min(sums)