算法

(DP) $O(nm)$

此题由（ 62. 不同路径 ）拓展而来，机器人每一时刻只能选择向下或者向右移动一步，网格中存在障碍物。对于障碍物我们需要分两种情况考虑，分别是处于网格边界和网格中央时的情况，根据题意很容易发现处于边界的障碍物，

• 左边界的第一个障碍物下面的所有边界点无法到达，
• 上边界的第一障碍物右边的所有边界点无法到达。

对于网格中的障碍物，到达此点的路径条数默认为0。

用数组dp表示可到达每个点的路径数

• 通过所有到达(i-1,j)这个点的路径往下走一步可到达(i,j), 这路径数总共有dp[i-1][j]条
• 通过所有到达(i,j-1)这个点的路径往右走一步可到达(i,j), 这路径数总共有dp[i][-1j]条

• 由此可以推出递推式dp[i][j] = dp[i-1][j]+dp[i][j-1]

• 如果数组长宽都为0的话返回0

• 设dp数组的大小与obstacleGrid数组大小一致

• 对于左边界，在第一个障碍物前面（或者到达边界）的所有点皆可到达
• 对于上边界，在第一个障碍物左边（或者到达边界）的所有点皆可到达
• 从dp[1][1]开始遍历网格，根据递推式dp[i][j] = dp[i-1][j]+dp[i][j-1]更新当前点可到达路径数
• 结果存在网格右下角，即dp[n-1][m-1]

C++ 代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
         //获取网格的长宽
        int n=obstacleGrid.size(),m=obstacleGrid[0].size();
        if (n == 0 || m == 0) {
            return 0;
        }
        int dp[n][m];
        memset(dp,0,sizeof(dp));
        if (obstacleGrid[0][0] == 0) {
            dp[0][0] = 1;
        }
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                //若遇到障碍物，则跳过
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }
                //对于上边界，第一个障碍物或边界左边的所有边界点皆可到达
                if (i == 0) {
                    dp[i][j] = dp[i][j-1];
                    continue;
                }
                //对于左边界，第一个障碍物或边界前的所有边界点皆可到达
                if (j == 0) {
                    dp[i][j] = dp[i-1][j];
                    continue;
                }
                //到达当前点的路径数等于能到达此点上面的点和左边点的路径数之和
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[n-1][m-1];
    }
};