leetcode
leetcode 51 ~ 100
不同路径 II

不同路径 II

难度:

标签:

题目描述

一个机器人位于一个 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

代码结果

运行时间: 48 ms, 内存: 15 MB

/*
题目思路：
我们使用Stream API来简化代码。创建一个一维数组dp，其中dp[j]表示到达当前行第j列的不同路径的数量。
1. 如果obstacleGrid[i][j] == 1，说明该位置有障碍物，dp[j] = 0。
2. 如果没有障碍物，则dp[j] += dp[j - 1]。
3. 初始化时，如果起始点有障碍物，直接返回0；否则，dp[0] = 1。
*/
import java.util.stream.IntStream;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[] dp = new int[n];
    dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
}

解释

方法:

这个题解使用动态规划的思路来解决问题。通过备忘录的方式，自底向上地计算从起点到终点的路径数。对于网格中的每个位置，如果该位置没有障碍物，那么到达该位置的路径数等于到达其上方位置的路径数加上到达其左方位置的路径数。在计算过程中，通过备忘录避免重复计算，提高效率。最终返回到达终点的路径数作为结果。

时间复杂度:

O(m*n)

空间复杂度:

O(m*n)

代码细节讲解

🦆
递归函数dp中，为什么在检查位置(i, j)是否有障碍物之前，先检查了(i-1, j)和(i, j-1)的位置？
▷
在动态规划中，我们需要从已知的基础情况（如起点或边界）出发，逐步建立到达更复杂位置的路径计算。在递归函数dp中，检查(i-1, j)和(i, j-1)的位置是为了根据已解决的子问题（这些子问题即到达上方和左方位置的路径数）来解决当前问题（即到达位置(i, j)的路径数）。该方法假设这些子问题已经被解决，所以在尝试计算当前位置的路径数之前，需要先获得这些必需的子问题的解。
🦆
在递归函数中，如果位置(i, j)本身就有障碍物，是否应该直接返回0而不是尝试向上或向左查找路径数？
▷
是的，如果位置(i, j)本身有障碍物，则应该直接返回0。在题解中，这一点应该在读取位置(i, j)的障碍物信息之后立即检查，因为如果当前位置不可通过，则不需要继续计算从上方或左方到达当前位置的路径数。这不仅避免了不必要的计算，也符合实际情况，即障碍物阻止了任何路径通过该位置。
🦆
为什么备忘录memo使用字典而不是二维数组，这种选择对性能有什么影响？
▷
备忘录memo使用字典而不是二维数组的主要原因是灵活性和空间效率。字典允许我们仅保存那些实际进行了计算的状态，从而在稀疏网格（大部分位置有障碍物的情况）中节省空间。相比之下，二维数组会为整个网格的每个位置分配空间，包括那些根本不会被访问的位置。因此，使用字典可能会在空间使用上更有效，尤其是在大规模或稀疏的网格中。
🦆
在计算路径时，如何处理边界情况，例如当i=0或j=0时，但对应的行或列存在障碍物的情况？
▷
处理边界情况时，需要特别注意i=0或j=0的情况。如果在边界行或列中存在障碍物，那么从该障碍物之后的所有位置都应该被视为无法到达。在递归函数中，可以通过检查边界行或列中每个位置是否存在障碍物，并据此更新路径计数来处理此问题。例如，如果第0行的某个位置j有障碍物，则该位置及其右侧的所有位置的路径数都应该是0。同理，对于第0列也应当如此处理。

相关问题

不同路径

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

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

问总共有多少条不同的路径？

 

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

 

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

不同路径 III

在二维网格 grid 上，有 4 种类型的方格：

  • 1 表示起始方格。且只有一个起始方格。
  • 2 表示结束方格，且只有一个结束方格。
  • 0 表示我们可以走过的空方格。
  • -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

 

示例 1：

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

示例 2：

输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径： 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

示例 3：

输入：[[0,1],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。

 

提示：

  • 1 <= grid.length * grid[0].length <= 20
不同路径最小路径和