LeetCode题练习与总结：不同路径Ⅱ--63

一、题目描述

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

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

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

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

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

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

二、解题思路

1. 初始化：dp[0][0]是起始点，如果obstacleGrid[0][0]为0，则dp[0][0] = 1，否则为0。表示没有路径可以到达起点上存在障碍物的网格。
2. 状态转移方程：对于dp[i][j]，它只能由dp[i-1][j]（从左边来）和dp[i][j-1]（从上边来）转移而来。如果obstacleGrid[i][j]为1，则表示该位置有障碍物，dp[i][j]为0。否则，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3. 遍历：从左到右，从上到下遍历obstacleGrid，根据状态转移方程更新dp数组。
4. 结果：最后dp[m-1][n-1]即为从左上角到右下角的不同路径数量。

三、具体代码

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

        // 初始化dp数组，所有元素初始为0
        int[][] dp = new int[m][n];

        // 如果起点有障碍物，则直接返回0
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // 初始化起点为1，表示从起点出发至少有一条路径
        dp[0][0] = 1;

        // 遍历网格
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果当前位置有障碍物，则跳过
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                // 从左边来
                if (i > 0) {
                    dp[i][j] += dp[i-1][j];
                }
                // 从上边来
                if (j > 0) {
                    dp[i][j] += dp[i][j-1];
                }
            }
        }

        // 返回到达右下角的路径数量
        return dp[m-1][n-1];
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 外层循环遍历每一行，内层循环遍历每一列，所以总共的循环次数是 m * n，其中 m 是网格的行数，n 是网格的列数。
• 在每次循环中，代码主要进行的是常数时间的操作，包括数组的读写操作和简单的加法运算。
• 由于没有嵌套循环或递归调用，且没有额外的复杂操作，所以时间复杂度是 O(m * n)。

2. 空间复杂度

• 空间复杂度主要由创建的二维数组 dp 决定，其大小为 m * n。
• dp 数组用于存储到达每个位置的路径数量，这是解决这个问题所需的额外空间。
• 代码中没有使用其他额外的数据结构或变量，所以空间复杂度是 O(m * n)。

五、总结知识点

1. 二维数组的使用：代码中使用了二维数组 dp 来存储从起点到每个位置的路径数量。这是动态规划问题中常见的数据结构，用于保存问题的子解。

2. 动态规划（Dynamic Programming）：这是一个典型的动态规划问题。动态规划是一种通过将问题分解为重叠的子问题，并存储子问题的解（通常是在一个表格中），从而避免重复计算子问题的解的优化技巧。

• 状态定义：dp[i][j] 表示从左上角到位置 (i, j) 的不同路径数量。
• 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1] 当 obstacleGrid[i][j] 为 0 时，表示没有障碍物，可以从上方或左方到达当前位置。
• 初始化：dp[0][0] 为 1，因为起点没有障碍物，且只有一条路径可以到达起点。

3. 条件判断：代码中使用了条件判断来处理障碍物的情况。如果当前位置有障碍物（obstacleGrid[i][j] == 1），则 dp[i][j] 被设置为 0，表示没有路径可以到达该位置。

4. 循环控制：代码使用了两层嵌套的 for 循环来遍历整个网格。外层循环遍历行，内层循环遍历列。这种循环结构适用于处理网格、矩阵等二维结构的问题。

5. 空间复杂度优化：尽管代码中没有直接体现，但在实际应用中，可以考虑使用一维数组来优化空间复杂度，因为 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i][j-1]，不需要整个二维数组 dp。

• 可以通过仅使用两行空间（一个用于当前行，一个用于前一行）来更新路径数量，从而将空间复杂度从 O(m * n) 降低到 O(min(m, n))。

6. 边界条件处理：代码在处理动态规划问题时，特别注意了边界条件。在这个问题中，起点 dp[0][0] 是一个特殊的边界条件，如果起点有障碍物，则没有路径可以到达，直接返回 0。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。