LC63. 不同路径 II

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 现在考虑网格中有障碍物。问总共有多少条不同的路径？ XMuYbSCIyo2aW0xkLzrcDzarnVh.png

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

题目解析

题目在说什么

想象你是一个小机器人，站在一个网格的左上角，要走到右下角。你每次只能往右走一格，或者往下走一格。但是！这个网格里有些格子是障碍物（比如石头），你不能踩上去。现在要你算一算：从起点到终点，总共有多少条不同的走法？

比如下面这个 3x3 的网格（0 表示空地，1 表示障碍物）：

[0, 0, 0]
[0, 1, 0]
[0, 0, 0]

中间那个 1 就是障碍物，你不能经过它。那么从左上角到右下角，有几种走法呢？答案是 2 种：先右再下再右再下，或者先下再右再下再右。注意，你不能绕过障碍物，只能避开它。

思路是怎么来的

这个问题其实是一个“路径计数”问题。如果你没有障碍物，那很简单：从左上角到右下角，你只能向右或向下，所以路径数就是组合数。但有了障碍物，我们就得想办法避开它们。

怎么想呢？我们可以用“动态规划”的思路，也就是把大问题拆成小问题。想象一下：你要到达某个格子 (i, j)，你只能从它的左边格子 (i, j-1) 过来，或者从它的上边格子 (i-1, j) 过来。所以，到达 (i, j) 的路径数，就等于到达左边格子的路径数加上到达上边格子的路径数。这个逻辑很自然，对吧？

但是，如果 (i, j) 本身就是一个障碍物，那你就根本到不了它，所以路径数就是 0。

那么，我们怎么开始呢？先看第一行和第一列。因为机器人只能向右或向下，所以第一行的格子只能从左边过来（也就是一直向右走），第一列的格子只能从上边过来（也就是一直向下走）。但是，如果第一行或第一列里出现了障碍物，那它后面的格子就都到不了了，因为必须经过那个障碍物。

所以，我们可以先处理第一行和第一列，然后从第二行第二列开始，用上面的规则一步步算出每个格子的路径数。最后，右下角那个格子的路径数就是答案。

代码逐步拆解

我们来看参考代码，一步步解释它在干什么。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 获取网格的行数和列数
        int m = obstacleGrid.length;      // 行数
        int n = obstacleGrid[0].length;   // 列数

        // 创建一个二维数组 dp，用来记录到达每个格子的路径数
        int[][] dp = new int[m][n];

这里，dp[i][j] 表示从起点 (0,0) 到达格子 (i,j) 有多少条不同的路径。一开始所有格子都是 0。

第一步：处理第一列

        // 遍历第一列的所有行
        for(int i = 0; i < m ; i++){
            // 如果当前格子是障碍物，那么它和它下面的所有格子都到不了
            if(obstacleGrid[i][0] == 1)  break;
            // 否则，只有一条路径（一直向下走）
            dp[i][0] = 1;
        }

第一列的格子只能从上面下来。所以，如果第一列的第一个格子是空地，那么到达它的路径只有 1 条（就是起点本身）。如果第二个格子也是空地，那么到达它也只有 1 条（从起点向下走一步）。但是，如果某个格子是障碍物，比如 obstacleGrid[2][0] == 1，那么它下面的所有格子（比如第3行、第4行...）都无法到达，因为必须经过这个障碍物。所以用 break 跳出循环，后面的格子保持默认的 0。

第二步：处理第一行

        // 遍历第一行的所有列
        for(int j = 0; j < n ; j++){   
            // 如果当前格子是障碍物，那么它和它右边的所有格子都到不了
            if(obstacleGrid[0][j] == 1) break;
            // 否则，只有一条路径（一直向右走）
            dp[0][j] = 1;
        }

同理，第一行的格子只能从左边过来。所以，如果第一个格子是空地，到达它只有 1 条路径。如果第二个格子也是空地，到达它也只有 1 条（从起点向右走一步）。遇到障碍物就停止，后面的格子都是 0。

第三步：填充剩余格子

        // 从第1行第1列开始，遍历所有格子
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 如果当前格子是障碍物，跳过它（dp[i][j] 保持为 0）
                if (obstacleGrid[i][j] == 1) continue;