63.py

'''
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?
'''

classSolution(object):
defuniquePathsWithObstacles(self, obstacleGrid):
"""
 :type obstacleGrid: List[List[int]]
 :rtype: int
 """
m, n=len(obstacleGrid), len(obstacleGrid[0])
dp= [[0for_inrange(n)] for_inrange(m)]

ifobstacleGrid[0][0] ==1orobstacleGrid[m-1][n-1] ==1:
return0

dp[0][0] =1
forindexinrange(1, m):
ifobstacleGrid[index][0] ==1:
dp[index][0] =0
else:
dp[index][0] =dp[index-1][0]

forindexinrange(1, n):
ifobstacleGrid[0][index] ==1:
dp[0][index] =0
else:
dp[0][index] =dp[0][index-1]

forindex_iinrange(1, m):
forindex_jinrange(1, n):
ifobstacleGrid[index_i][index_j] ==1:
dp[index_i][index_j] =0
else:
dp[index_i][index_j] =dp[index_i-1][index_j] +dp[index_i][index_j-1]

returndp[m-1][n-1]