动态规划——63. 不同路径 II

柔光的暖阳◎ 2023-10-08 16:17 31阅读 0赞

## 1 题目描述 ##

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

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

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

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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/unique-paths-ii

## 2 题目示例 ##

![在这里插入图片描述][a58fb821dc8a4ce68746df9214a5ceec.png]  
输入：obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]  
输出：2  
解释：3x3 网格的正中间有一个障碍物。  
从左上角到右下角一共有 2 条不同的路径：

1.  向右 -> 向右 -> 向下 -> 向下
2.  向下 -> 向下 -> 向右 -> 向右

![在这里插入图片描述][88e9dbd5ea8e4581bcee052d8382a172.png]  
输入：obstacleGrid = \[\[0,1\],\[0,0\]\]  
输出：1

## 3 题目提示 ##

m == obstacleGrid.length  
n == obstacleGrid\[i\].length  
1 <= m, n <= 100  
obstacleGrid\[i\]\[j\] 为 0 或 1

## 4 思路 ##

这道题相对于62.不同路径 (opens new window)就是有了障碍。

第一次接触这种题目的同学可能会有点懵，这有障碍了，应该怎么算呢？

62.不同路径 (opens new window)中我们已经详细分析了没有障碍的情况，有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。  
动规五部曲：

确定dp数组（dp table）以及下标的含义  
dp\[i\]\[j\] ：表示从（0 ，0）出发，到(i, j) 有dp\[i\]\[j\]条不同的路径。

确定递推公式  
递推公式和62.不同路径一样，dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\]。

但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。  
所以代码为：

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

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

本题是62.不同路径 (opens new window)的障碍版，整体思路大体一致。

但就算是做过62.不同路径，在做本题也会有感觉遇到障碍无从下手。

其实只要考虑到，遇到障碍dp\[i\]\[j\]保持0就可以了。

也有一些小细节，例如：初始化的部分，很容易忽略了障碍之后应该都是0的情况。

本题思路采自代码随想录  
链接：[https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html\#%E6%80%9D%E8%B7%AF][https_programmercarl.com_0063._E4_B8_8D_E5_90_8C_E8_B7_AF_E5_BE_84II.html_E6_80_9D_E8_B7_AF]

## 5 我的答案 ##

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int n = obstacleGrid.length, m = obstacleGrid[0].length;
            int[][] dp = new int[n][m];
    	
            for (int i = 0; i < m; i++) {
        
    	    if (obstacleGrid[0][i] == 1) break; //一旦遇到障碍，后续都到不了
    	    dp[0][i] = 1;
            }
            for (int i = 0; i < n; i++) {
        
    	    if (obstacleGrid[i][0] == 1) break; 一旦遇到障碍，后续都到不了
    	    dp[i][0] = 1;
            }
            for (int i = 1; i < n; i++) {
        
                for (int j = 1; j < m; j++) {
        
                    if (obstacleGrid[i][j] == 1) continue;
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[n - 1][m - 1];
        }
    }

[a58fb821dc8a4ce68746df9214a5ceec.png]: https://img-blog.csdnimg.cn/a58fb821dc8a4ce68746df9214a5ceec.png
[88e9dbd5ea8e4581bcee052d8382a172.png]: https://img-blog.csdnimg.cn/88e9dbd5ea8e4581bcee052d8382a172.png
[https_programmercarl.com_0063._E4_B8_8D_E5_90_8C_E8_B7_AF_E5_BE_84II.html_E6_80_9D_E8_B7_AF]: https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html#%E6%80%9D%E8%B7%AF