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.For example,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.
这题的做法和前面的unique path是一样的，都是用的动态规划。不同之处在于需要判断有没有点为1.
直接上代码：
class Solution:# @param obstacleGrid, a list of lists of integers# @return an integerdef uniquePathsWithObstacles(self, obstacleGrid):rown=len(obstacleGrid)coln=len(obstacleGrid[0])dp=[[0 for i in range(coln)] for j in range(rown)]if obstacleGrid[0][0]!=1:dp[0][0]=1for row in range(1,rown):if obstacleGrid[row][0]!=1 and dp[row-1][0]==1:dp[row][0]=1else:breakfor col in range(1,coln):if obstacleGrid[0][col]!=1 and dp[0][col-1]==1:dp[0][col]=1else:breakfor row in range(1,rown):for col in range(1,coln):if obstacleGrid[row][col]==1:dp[row][col]=0else:dp[row][col]=dp[row-1][col]+dp[row][col-1]return dp[rown-1][coln-1]
，闹里有钱，静处安身。
