Unique Paths II – LeetCode题目：
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 as1and0respectively 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 is2.
分析：这道题目和Minimum Path Sum，Unique Paths（点击打开链接）的思想一样，都是直接动态规划就可以。在grid[a][b]这一块时，我们只能从grid[a][b-1]和grid[a-1][b]到这一块，而从第一块能到这一块的路径总共有多少呢？等于到grid[a][b-1]和grid[a-1][b]的路径数相加。而当一直推到a = 1 和 b=1 时，我们到grid[a][b]的路径 = grid[a][b-1]和grid[a-1][b] ，， 即grid[1][0]和grid[1][0]，而这两个都等于1，因为只能从grid[0][0]到这两个点。至于最上面和最左面的边缘点，只能从grid[0][0]移动到，所以为1.代码：class Solution:# @param obstacleGrid, a list of lists of integers# @return an integerdef uniquePathsWithObstacles(self, obstacleGrid):if not obstacleGrid:return 0if obstacleGrid[0][0]== 0:obstacleGrid[0][0]=1else:return 0m,n =len(obstacleGrid),len(obstacleGrid[0])for j in xrange(0,n):for i in xrange(0,m):if obstacleGrid[i][j] == 1 and (i != 0 or j != 0):obstacleGrid[i][j] = 0elif i == 0 and j == 0:continueelif i == 0:obstacleGrid[i][j] = obstacleGrid[i][j-1]elif j == 0:obstacleGrid[i][j] = obstacleGrid[i-1][j]else:obstacleGrid[i][j] = obstacleGrid[i-1][j]+obstacleGrid[i][j-1]return obstacleGrid[m-1][n-1]
曾经一直想让别人知道自己的心情，那些沉重，
