05_不同路径2(带障碍物版)

简介: 05_不同路径2(带障碍物版)

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

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

【思路】

动规五部曲:

1、确定dp数组以及下标的含义

dp[i][j]:表示从(0,0)出发,到(i,j)有dp[i][j]条不同的路径。

2、确定递推公式

递推公式和上面那题一样,dp[i][j] = dp[i-1][j]+dp[i][j-1]。

但这里需要注意的是,因为有了障碍的话应该就保持初始状态(初始状态为0)。

if (obstacleGrid[i][j] == 0) {//当(i, j)没有障碍的时候,再推导dp[i][j]
  dp[i][j] = dp[i-1][j] + dp[i][j-1];
}

3、dp数组如何初始化

int[][] dp = new int[m][n];
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

因为从(0,0)的位置到(i,0)的路径只有一条,所以dp[i][0]一定为1,dp[0][j]也同理。

但如果(i, 0)这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。

注意代码里for循环的终止条件,一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作,dp[0][j]同理

4、确定遍历顺序

从递归公式dp[i][j]=dp[i-1][j]+dp[i][j-1]中可以看出,一定是从左到右一层一层遍历,这样保证推导dp[i][j]的时候,dp[i-1][j]和dp[i][j-1]一定有数值。

for(int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    if(obstacleGrid[i][j] == 1) continue;
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
  }
}

5、举例推导dp数组

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        //如果在起点或终点出现了障碍,直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
            }
        }
        return dp[m - 1][n - 1];
    }
}
相关文章
|
C++
C++语言中流程控制
C++语言中流程控制
263 0
|
编译器 C++
【C++】类与对象(static、explicit、友元、隐式类型转换、内部类、匿名对象)
【C++】类与对象(static、explicit、友元、隐式类型转换、内部类、匿名对象)
286 2
|
C++
C++ While 和 For 循环:流程控制全解析
本文介绍了C++中的`switch`语句和循环结构。`switch`语句根据表达式的值执行匹配的代码块,可以使用`break`终止执行并跳出`switch`。`default`关键字用于处理没有匹配`case`的情况。接着,文章讲述了三种类型的循环:`while`循环在条件满足时执行代码,`do/while`至少执行一次代码再检查条件,`for`循环适用于已知循环次数的情况。`for`循环包含初始化、条件和递增三个部分。此外,还提到了嵌套循环和C++11引入的`foreach`循环,用于遍历数组元素。最后,鼓励读者关注微信公众号`Let us Coding`获取更多内容。
501 0
|
存储 算法 Python
python算法(二)—栈、队列、链表、哈希
python算法(二)—栈、队列、链表、哈希
441 0
|
编译器 C++
C++ 类和对象(静态的static、友元、内部类、匿名对象、explicit)知识点+完整思维导图+实操图+深入细节通俗易懂建议收藏(二)
C++ 类和对象(静态的static、友元、内部类、匿名对象、explicit)知识点+完整思维导图+实操图+深入细节通俗易懂建议收藏(二)
|
C++
【剑指offer】剑指 Offer 09. 用两个栈实现队列(C++ 模拟 栈 队列)
【剑指offer】剑指 Offer 09. 用两个栈实现队列(C++ 模拟 栈 队列)
230 0
|
开发工具 git C++
git pull VS git fetch&merge(good)
从图中可以看到,git fetch和git pull的区别, git fetch 不会自动的将结果merge到本地,只是将远程版本同步到本地版本库,而不会merge到本地副本。 git pull  将会直接把working directory中的内容覆盖掉。
2148 0