class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if obstacleGrid[-1][-1]==1 or obstacleGrid[0][0]==1:
return 0
dp=[[0]*len(obstacleGrid[0]) for x in range(len(obstacleGrid))]
for m in range(len(obstacleGrid)):
if obstacleGrid[m][0]==0:
dp[m][0]=1
else:
break #这里的跳出真漂亮，如果不跳出则阻碍的地方的后面也会被误算为可走路径，所以直接跳出意味着阻碍影响的位置有那些
for n in range(len(obstacleGrid[0])):
if obstacleGrid[0][n]==0:
dp[0][n]=1
else:
break
for i in range(1,len(obstacleGrid)):
for j in range(1,len(obstacleGrid[0])):
if obstacleGrid[i][j]==1:
dp[i][j]=0
else:
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]
https://www.youtube.com/watch?v=-7lvth2fJ24
