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 3x3 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，使用DP。区别在于怎么处理障碍物。如果obstacleGrid[i,j] == 1，那么显然DP[i,j] = 0。
1 class Solution(object): 2 def uniquePathsWithObstacles(self, obstacleGrid): 3 """ 4 :type obstacleGrid: List[List[int]] 5 :rtype: int 6 """ 7 m = len(obstacleGrid) 8 n = len(obstacleGrid[0]) 9 10 dp = [[0]*n for x in range(m)] 11 12 if obstacleGrid[0][0] == 1: 13 return 0 14 else: 15 dp[0][0] = 1 16 17 for i in range(m): 18 for j in range(n): 19 if i == 0 and j == 0: 20 continue 21 if obstacleGrid[i][j] == 1: 22 dp[i][j] = 0 23 else: 24 if j == 0: 25 dp[i][j] = dp[i-1][j] 26 elif i == 0: 27 dp[i][j] = dp[i][j-1] 28 else: 29 dp[i][j] = dp[i][j-1] + dp[i-1][j] 30 31 return dp[-1][-1] 32
原文：http://www.cnblogs.com/lettuan/p/6349437.html