⚡Flashcard Drill➔
NeetCode #713LC-63Medium2-D Dynamic ProgrammingNC 250
← Back to All Problems

#713 · #63 · Unique Paths II(不同路径 II)

📌 Problem Statement & Constraints

A robot moves right or down from the top-left to the bottom-right of an m x n grid that contains obstacles marked 1. Return the number of distinct paths; obstacles may not be entered. Constraints: 1 <= m, n <= 100, obstacleGrid[i][j] is 0 or 1.

💡 Core Algorithmic Approaches

  1. Use the same DP as Unique Paths, but a blocked cell has zero paths.
  2. In the rolling row, set dp[j] = 0 when the cell is blocked, otherwise dp[j] += dp[j-1].
  3. The first row and column are handled naturally: an obstacle zeroes everything after it in that line.
  4. If the start or the goal is blocked, the result is 0.

💻 Benchmark Python3 Implementation

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * n
        dp[0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0              # blocked cell
                elif j > 0:
                    dp[j] += dp[j - 1]     # above + left
        return dp[n - 1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): one pass over the grid.
💾 Space Complexity
O(n): a single row.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to zero a blocked cell: the value from the row above would leak through and overcount.
  • Seeding dp[0] = 1 blindly: it works only because the start cell is processed first and zeroed if blocked.
  • Reusing a 2-D table with the wrong base: the rolling row relies on dp[j-1] already holding the current row's value.
  • Handling the goal obstacle separately: it is covered by the same blocked-cell rule.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems