# 不同路径 II

<p>一个机器人位于一个 <em>m x n </em>网格的左上角 （起始点在下图中标记为“Start” ）。</p>
<p>机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。</p>
<p>现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？</p>
<p><img src="https://img-blog.csdnimg.cn/img_convert/dcc604a2757b6fd0e6bdc5155c945ffc.png#pic_center" /></p>
<p>网格中的障碍物和空位置分别用 <code>1</code> 和 <code>0</code> 来表示。</p>

<p><strong>示例 1：</strong></p><img alt=""
    src="https://img-blog.csdnimg.cn/img_convert/d127c16fad8048e19db6f2a2bea73240.png#pic_center" />
<pre><strong>输入：</strong>obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]<strong><br />输出：</strong>2<strong><br />解释：</strong>3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：<br />1. 向右 -> 向右 -> 向下 -> 向下<br />2. 向下 -> 向下 -> 向右 -> 向右</pre>
<p><strong>示例 2：</strong></p><img alt=""
    src="https://img-blog.csdnimg.cn/img_convert/d95382b3c9b30e83be3e383421106a67.png#pic_center" />
<pre><strong>输入：</strong>obstacleGrid = [[0,1],[0,0]]<strong><br />输出：</strong>1</pre>

<p><strong>提示：</strong></p>
<ul>
    <li><code>m == obstacleGrid.length</code></li>
    <li><code>n == obstacleGrid[i].length</code></li>
    <li><code>1 <= m, n <= 100</code></li>
    <li><code>obstacleGrid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>
</ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    int a = 2;
    int b = 4;
    vector<vector<int>> obstacleGrid = vector<vector<int>>(a, vector<int>(b)) = {{0, 0, 0, 0}, {0, 1, 2, 3}};
    int res;

    res = sol.uniquePathsWithObstacles(obstacleGrid);
    cout << res;
    return 0;
}
```

## 答案

```c
class Solution
{
public:
    int dp[110];
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
            return 0;
        dp[1] = 1;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (obstacleGrid[i - 1][j - 1] == 0)
                    dp[j] += dp[j - 1];
                else
                    dp[j] = 0;
            }
        }
        return dp[n];
    }
};
```
## 选项


### A

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

### B

```c
class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        int p[m][n];

        int k = 0;
        while (k < m && obstacleGrid[k][0] != 1)
            p[k++][0] = 1;

        while (k < m)
            p[k++][0] = 0;

        k = 0;
        while (k < n && obstacleGrid[0][k] != 1)
            p[0][k++] = 1;
        while (k < n)
            p[0][k++] = 0;

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
            {
                if (obstacleGrid[i][j] == 1)
                    p[i][j] = 0;
                else
                    p[i][j] = p[i - 1][j] + p[i][j - 1];
            }
        return p[m - 1][n - 1];
    }
};
```

### C

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