原题网址：

描述

"" 的跟进问题：

现在考虑网格中有障碍物，那样将会有多少条不同的路径？

网格中的障碍和空位置分别用 1 和 0 来表示。

m 和 n 均不超过100

您在真实的面试中是否遇到过这个题？  是

样例

如下所示在3x3的网格中有一个障碍物：

[  [0,0,0],  [0,1,0],  [0,0,0]]

一共有2条不同的路径从左上角到右下角。

标签

数组

动态规划(DP)

 

思路：方法同不同的路劲类似，只不过要注意有障碍物的情况。有障碍物的地方dp值为0，这里尤其注意如果第一个点（0,0）就是障碍物，则整个grid无法走通，直接return 0即可。同理，初始化第一行、第一列时，如果遇到一个障碍物，后面的dp值全为0。

AC代码：

class Solution {public:    /**     * @param obstacleGrid: A list of lists of integers     * @return: An integer     */    int uniquePathsWithObstacles(vector
        
         
          > &obstacleGrid) {        // write your code here        int row=obstacleGrid.size();    if (row==0)    {        return 0;    }    int col=obstacleGrid[0].size();    if (col==0)    {        return 0;    }    vector
          
           
            > dp(row,vector
            
             (col,0));    if (obstacleGrid[0][0]==0)    {        dp[0][0]=1;    }    else//如果第一步都走不通，说明无法到达右下角，直接返回0;    {        return 0;    }    for (int i=1;i
            
           
          
         
        

 

其他实现方式：