Unique Path II
Problem: Unique Path II
We can basically use solution to Unique Path, except for position with obstacle there's no solution, which means 0.
Code in Python:
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if obstacleGrid[0][0] == 1: return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0] * n for _ in xrange(m)]
dp[0][0] = 1
for i in xrange(1, m):
dp[i][0] = 0 if obstacleGrid[i][0] else dp[i-1][0]
for j in xrange(1, n):
dp[0][j] = 0 if obstacleGrid[0][j] else dp[0][j-1]
for i in xrange(1, m):
for j in xrange(1, n):
dp[i][j] = 0 if obstacleGrid[i][j] else dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]