动态规划---不同路径 (II) Posted on 2021-08-30 00:00:00 2021-08-30 00:00:00 by Author 摘要 给定一个网格,你从起始点开始,每一次只能往下或者往右走,其中某些位置有障碍物，有障碍物的地方走不通，那么你能知道到达终点有多少种路径吗??? # 动态规划---不同路径 (II) 1. - 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ - **提示：** - m == obstacleGrid.length - n == obstacleGrid[i].length - 1 <= m, n <= 100 - obstacleGrid[i][j] 为 0 或 1 2. 示例描述 - 示例一  ```java 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右 ``` - 示例二  ```java 输入：obstacleGrid = [[0,1],[0,0]] 输出：1 ``` 3. 解题思路 - 这道题是[动态规划---不同路径(I)](http://www.geticsen.cn/view/articles/detail/cf993bdc-d811-496a-a279-463bb3667cb8)的一个变体，就是在所给网格的某个位置添加了一个障碍物，其实这也不妨碍我们沿用上一道题的解法思想，即就是，每到达一个地方都有两种来源，一个就是从上方来的，还有一个就是从左方来的，而题目说了，算出到达目的地的总路径，那么每到达一个地方，它的总路径就是从上方来的总路径与从左方来的总路径之和，就是到达这个地方所有路径了。但是如果某个位置有障碍物，那么到达此位置的路径总和就为0，因为此路不通，即就是到达此位置没有路径。这也就是在上一道题多余的思考的地方。 - 那么对于DP初始化来说，那么对于第一行，没有从上方来的路径，只有从左方来的路径，而且移动只能从上到下，从左到右，那么第一行每个位置都是从左方移动来的，但是第一行某个位置有障碍物，那么从此位置开始，之后所有的位置路径都为0(限于第一行)，因为第一行某个位置有障碍物，那么到达此位置路径和为0，那么此位置之后路径和也为0(第一行某位置的路径和都是从左侧走过来的)。同理第一列也是，只有从上方来的路径，没有从左方来的路径，第一列某个位置有障碍物，那么从此障碍物之后的一系列位置都走不通，及就是路径和为0。这样对于其他的位置，都可以从上方来，或者从左方来，所以其他位置的总路径就是上方路径和与左方路径的和，如果其他位置有障碍物，那么有障碍物的位置路径和为0，因为没有一条路径可以到达有障碍物的地方。而本题要求算出最后一个位置的路径和，那么遍历所有的位置，返回最后一个位置的路径即可。 - 本题也非常简单，并且也是动态规划经典的入门题，实现起来也非常简单，具体实现如下所示。 4. 代码示例 ```java public int uniquePathsWithObstacles(int[][] obstacleGrid) { //定义网格的长宽 int m=obstacleGrid.length; int n=obstacleGrid[0].length; int [][]dp=new int[m][n]; //考虑边界条件 if (m == 0) { return 0; } //DP初始化操作 //如果第一行的某个位置有障碍物，那么这一行再次之后所有的位置都不能通过 //否则到达此位置的路径只有一条 //因为只能玩右或者往下走,第一行的位置只能往右走，所以只有一条路径 for (int i = 0; i <n && obstacleGrid[0][i]==0 ; i++) { dp[0][i]=1; } //同理第一列的路径与第一行的道理相似 //第一列的位置只能从上往下走， //当遇到第一个障碍物之后，第一列之后所有的位置路径都为0，都不能通过 for (int i = 0; i <m&&obstacleGrid[i][0]==0 ; i++) { dp[i][0]=1; } //之后就从第二行，第二列开始 //如果所给定网格的某一位置为障碍物，那么此位置不同，也就是到达此位置的路径为0 //否则此位置可以通行，那么此位置的路径总和就是其左边路径和与上边的路径总和 for (int i =1; i <m ; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { continue; } else { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } //确定完每个位置的路径总和之后，到达最下角的路径即为dp数组最后一个元素的值 //返回即可 return dp[m-1][n-1]; } ```
{{ item.content }}
{{ child.content }}