Same robot, same moves (only right or down), but now the grid obstacleGrid has obstacles marked with 1 and free cells marked with 0. The robot cannot step on an obstacle. Return the number of distinct paths from the top-left to the bottom-right corner.
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1
- The answer is at most 2 * 10^9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every right/down path, which is exponential. State: dp[r][c] = number of paths reaching (r, c). Recurrence: if the cell is an obstacle, dp[r][c] = 0; otherwise dp[r][c] = dp[r-1][c] + dp[r][c-1]. Base case: dp[0][0] = 1 if the start is free, else 0. Unlike the plain version, the first row and column are not all 1: everything after an obstacle in the first row is unreachable. Processing in row order with one 1D array handles that automatically, because a blocked cell resets to 0 and the zero flows right and down.
Algorithm
- Create
rowof lengthnfilled with 0 and setrow[0] = 1if the start is free. - For each row
rand each columnc: - If the cell is an obstacle, set
row[c] = 0. - Otherwise, if
c > 0, addrow[c - 1]torow[c]. - Return
row[n - 1].
O(m * n)Space: O(n)class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m, n = len(obstacleGrid), len(obstacleGrid[0]) row = [0] * n row[0] = 1 if obstacleGrid[0][0] == 0 else 0 for r in range(m): for c in range(n): if obstacleGrid[r][c] == 1: row[c] = 0 # blocked elif c > 0: row[c] += row[c - 1] # above + left return row[n - 1]