How do obstacles affect the DP state transition in Unique Paths II?

Obstacles are treated as cells with 0 paths. In the DP transition, any cell that is blocked does not contribute to the cumulative path count, ensuring that no paths go through obstacles.

What is the time and space complexity of this approach?

The DP solution iterates over all m*n cells, giving O(m*n) time. Using a 2D table is O(m*n) space, but optimized 1D row storage reduces space to O(n).

Can the robot move diagonally in Unique Paths II?

No, the robot can only move right or down. Any DP approach must account only for these directions when summing paths to each cell, respecting obstacle placement.

What should be returned if the start or end cell is an obstacle?

If either the top-left or bottom-right cell is blocked, the robot cannot start or finish, so the function should immediately return 0 without computing the DP table.

How can I optimize memory usage for larger grids?

Use a single 1D array representing the current row and update it in place by summing left and previous row values, skipping obstacle cells to reduce memory while keeping DP logic correct.

#63

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

不同路径 II

给定一个 m x n 的整数数组 grid 。一个机器人初始位于左上角（即 grid[0][0] ）。机器人尝试移动到右下角（即 grid[m - 1][n - 1] ）。机器人每次只能向下或者向右移动一步。网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何…

数组动态规划矩阵

题目描述

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 10⁹。

示例 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

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $\textit{dfs}(i, j)$ 表示从网格 $(i, j)$ 到网格 $(m - 1, n - 1)$ 的路径数。其中 $m$ 和 $n$ 分别是网格的行数和列数。

函数 $\textit{dfs}(i, j)$ 的执行过程如下：

如果 $i \ge m$ 或者 $j \ge n$ ，或者 $\textit{obstacleGrid}[i][j] = 1$ ，则路径数为 $0$ ；
如果 $i = m - 1$ 且 $j = n - 1$ ，则路径数为 $1$ ；
否则，路径数为 $\textit{dfs}(i + 1, j) + \textit{dfs}(i, j + 1)$ 。

为了避免重复计算，我们可以使用记忆化搜索的方法。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是网格的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n or obstacleGrid[i][j]:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            return dfs(i + 1, j) + dfs(i, j + 1)

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        return dfs(0, 0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you recognize how obstacles affect the standard unique paths DP formula?
question_mark
Can you optimize space while maintaining correct path counts through the state transition?
question_mark
Will you handle edge cases where the start or end cell is blocked?

warning

常见陷阱

外企场景

error
Forgetting to set paths to 0 in cells that contain obstacles, which can inflate path counts.
error
Not properly initializing the first row and column, leading to incorrect cumulative sums when obstacles exist.
error
Assuming all grids have at least one valid path, ignoring cases where the start or end cell is an obstacle.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Unique Paths I: No obstacles, simpler DP state transition with guaranteed paths.
arrow_right_alt
Count Paths with Diagonal Moves: Allow right, down, and diagonal movements, adjusting DP transitions.
arrow_right_alt
Minimum Path Sum with Obstacles: Compute the path with the minimal sum of cell values while avoiding obstacles.

help

常见问题

外企场景

继续练习

#64 最小路径和 #85 最大矩形 #221 最大正方形