Unique Paths II
Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
There is one obstacle in the middle of a 3×3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0] ]
The total number of unique paths is 2.
Note: m and n will be at most 100.
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/unique-paths-ii ## Basic Ideas: dynamic programming ## Very similar to https://code.dennyzhang.com/unique-paths ## ## f(i, j) = if it's obstacle, 0 ## else: f(i-1, j) + f(i, j-1) ## ## Complexity: Time O(m*n), Space O(m*n) class Solution(object): def uniquePathsWithObstacles(self, obstacleGrid): """ :type obstacleGrid: List[List[int]] :rtype: int """ row_count = len(obstacleGrid) if row_count == 0: return 0 col_count = len(obstacleGrid) # use default values to simplify the code matrix = [[0 for x in xrange(col_count)] for y in xrange(row_count)] matrix = 1 if obstacleGrid == 0 else 0 # first row i = 0 for j in range(1, col_count): if obstacleGrid[i][j] == 0: matrix[i][j] = matrix[i][j-1] # first column j = 0 for i in range(1, row_count): if obstacleGrid[i][j] == 0: matrix[i][j] = matrix[i-1][j] # others for i in range(1, row_count): for j in range(1, col_count): if obstacleGrid[i][j] == 0: matrix[i][j] = matrix[i-1][j] + matrix[i][j-1] return matrix[-1][-1]