Question: https://oj.leetcode.com/problems/unique-paths-ii/
Question Name: Unique Paths II
Similar with these questions: Minimum Path Sum and minimum edit distance.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution: # @param obstacleGrid, a list of lists of integers # @return an integer def uniquePathsWithObstacles(self, obstacleGrid): # COmpute the dimensions rowLen = len(obstacleGrid) colLen = len(obstacleGrid[0]) # Compute the number of possible path in the first column possiblePathCount = [0] * rowLen possiblePathCount[0] = 1 # Compute the number of possible path in the remaining column for colIndex in xrange(colLen): if obstacleGrid[0][colIndex] == 1: # This cell is obstacle. Impossible to reach here. possiblePathCount[0] = 0 for rowIndex in xrange(1, rowLen): if obstacleGrid[rowIndex][colIndex] == 1: # This cell is obstacle. Impossible to reach here. possiblePathCount[rowIndex] = 0 else: # We may reach here by moving from either left or upper cell. possiblePathCount[rowIndex] += possiblePathCount[rowIndex-1] return possiblePathCount[-1] |
The extra space can be saved if the input vector can be reused.