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
- Use the same DP as Unique Paths, but a blocked cell has zero paths.
- In the rolling row, set
dp[j] = 0when the cell is blocked, otherwisedp[j] += dp[j-1]. - The first row and column are handled naturally: an obstacle zeroes everything after it in that line.
- 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] = 1blindly: 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.