与上一题相比

不同之处在于有了obstacle，差别在于到每个obstacle的可能路径个数为0。
用一个dp数组来维护每一行便利完之后的路径个数，只是在更新dp数组时需要考虑obstacleGrid数组相应位子的值是否为0

我的AC代码

class Solution {
    //如果obstacles的值为1，则此位置的值设为0
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();//行数
        int n=obstacleGrid[0].size();//列数
        vector<int> dp(n+1,0);
        dp[1]=1;
        for(int i=0;i<m;i++)//
            for(int j=1;j<=n;j++)
            {
                if(obstacleGrid[i][j-1]==1)
                    dp[j]=0;
                else
                    dp[j]+=dp[j-1];
            }
      return dp.back();  
    }
};

最优解

时间上优于我的解法（目前还没找到原因），空间上没有单数组维护申请的额外空间少

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid.at(0).size();
        int path[m + 1][n + 1];
        for (int i = 0; i < (m + 1); i++) path[i][0] = 0;
        for (int i = 0; i < (n + 1); i++) path[0][i] = 0;
        for (int i = 1; i < (m + 1); i++) {
            for (int j = 1; j < (n + 1); j++) {
                if (obstacleGrid.at(i - 1).at(j - 1) == 1) path[i][j] = 0;
                else {
                    if ((i == 1) && (j == 1)) {
                        path[i][j] = 1;
                    } else {
                        path[i][j] = path[i - 1][j] + path[i][j - 1];
                    }
                }
            }
        }
        return path[m][n];
    }
};