【动态规划】06路径问题_不同路径II_C++（medium）

题目链接：leetcode不同路径II

---

目录

题目解析：

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码

---

题目解析：

题目让我们求在考虑网格中有障碍物的情况下，从左上角到右下角将会有多少条不同的路径

由题可得：

机器人位于一个?m x n?网格的左上角?

机器人每次只能向下或者向右移动一步

我们拿示例1来分析：

则根据题目要求我们只能向下或者向右移动一步，不能向上或向左回退，而且要避开障碍物；

所以这里我们一共有2种走法：

---

算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义（是什么？）

dp[i][j]表示到达i*j时一共有多少种方式；

这种状态表示怎么来的？

1.题目要求

经验：以i*j位置为结尾，

题目让我们求到达右下角有多少种方式（需要避开障碍物），那么这里我们可以dp[i][j]来表示。

所以这里我们用i*j表示右下角位置；

2.经验+题目要求

用之前或者之后的状态，推导出dp[i][j]的值；

根据最近的最近的一步，来划分问题

我们先不考虑有障碍物的情况：

当机器人到达dp[i-1][j]时，我们知道它到达[i-1][j]有dp[i-1][j]方式，

此时只需要从[i-1][j]往下走一步就可以到达目标位置，即：

……-->[i-1][j]-->(往下走一步)[i][j]；

……-->[i-1][j]-->(往下走一步)[i][j]；

……-->[i-1][j]-->(往下走一步)[i][j]；

……

所以往下走一步就可以到达目标位置的方式就有dp[i-1][j]种；

那么同理，

当机器人到达dp[i][j-1]时，我们知道它到达[i][j-1]有dp[i][j-1]方式，

此时只需要在到达[i][j-1]方式的后面往右边走一步就可以到达目标位置，即：

……-->[i][j-1]-->(往右边走一步)[i][j]；

……-->[i][j-1]-->(往右边走一步)[i][j]；

……-->[i][j-1]-->(往右边走一步)[i][j]；

……

所以往右边走一步就可以到达目标位置的方式就有dp[i-1][j]种；

综上所述，我们只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到，到达[i][j]位置的总方法，

即：

dp[i][j]=dp[i-1][j]+dp[i][j-1];

好，分析完了没有障碍物的情况，现在我们再来加上障碍物：

从上面的分析我们知道到达i*j位置，只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到

如果[i][j-1]与[i-1][j]之中有一个是障碍物时：

那么有效的路线就只有上面那条，那么只要把有障碍物的地方设为0，就不会影响状态转移方程了。

2.状态转移方程

dp[i]等于什么？

由我们的状态转移方程得：

在0行0列的时候越界，所以我们这里可以在m*n的外围多加1行1列，如图：

还有一个问题是：

我们要拿新增用来初始化的行和列要初始化为几呢？

假设：如果所需要到达的位置就在机器人所在的位置，此时有一种方式；

根据状态转移方程，在[0][1]与[1][0]位置要有一个位置需要初始化为1，其他位置初始化为0

我们这里选择[0][1]初始化为1

3.初始化

(保证填表的时候不越界)

4.填表顺序

（为了填写当前状态的时候，所需要的状态已经计算过了）

这里所需要的状态是：到达该位置的上面和左边位置的方式

所以填表顺序：

从上到下填写每一行

从左到右填写每一列

5.返回值

（根据题目要求和状态表示）

综上分析：

返回值为：dp[m][n];

---

编写代码:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    //1.创建dp表
    //2.初始化
    //3.填表
    //4.返回结果
    int m=obstacleGrid.size();
    int n=obstacleGrid[0].size();
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    dp[0][1]=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(obstacleGrid[i-1][j-1]==1)
            {
                dp[i][j]=0;
            }
            else
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    return dp[m][n];
    }
};