To solve this problem, we need to determine the number of unique paths from the top-left corner to the bottom-right corner of a grid, where movement is restricted to right or down directions, and some cells are obstacles.
Approach
The problem can be efficiently solved using dynamic programming (DP) with space optimization. Here's the step-by-step approach:
-
Edge Cases:
- If the start cell (0,0) is an obstacle, return 0 immediately.
- If the grid is empty, return 0.
-
DP Array Initialization:
- Use a 1D DP array of size
n(number of columns) to store the number of paths to each cell in the current row. This optimizes space from O(mn) to O(n).
- Use a 1D DP array of size
-
First Row Handling:
- For the first row, the number of paths to a cell is the same as the path count to the cell immediately left (if no obstacle is present).
-
Subsequent Rows Handling:
- For each row, update the DP array:
- If the current cell is an obstacle, set its path count to 0.
- Otherwise, the path count to the current cell is the sum of paths from the cell above (stored in the DP array) and the cell to the left (current row's left cell).
- For each row, update the DP array:
Solution Code
def uniquePathsWithObstacles(obstacleGrid):
m = len(obstacleGrid)
if m == 0:
return 0
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1:
return 0
dp = [0] * n
dp[0] = 1 # Start cell
# Fill first row
for j in range(1, n):
if obstacleGrid[0][j] == 0:
dp[j] = dp[j-1]
else:
dp[j] = 0
# Fill remaining rows
for i in range(1, m):
# Update first column of current row
if obstacleGrid[i][0] == 1:
dp[0] = 0
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[j] = 0
else:
dp[j] += dp[j-1] # Add paths from left (current row) to paths from above (previous row)
return dp[-1]
Explanation
- 1D DP Array: The DP array
dp[j]represents the number of unique paths to reach cell(i,j)(current rowi, columnj). - First Row: Since we can only move right, the path count to each cell in the first row is the same as the left cell (if no obstacle).
- Subsequent Rows: For each cell, if it's not an obstacle, the path count is the sum of paths from the cell above (stored in
dp[j]) and the cell to the left (stored indp[j-1]). This works because the DP array retains values from the previous row until updated.
This approach efficiently computes the number of unique paths with optimal space complexity, making it suitable for large grids. The time complexity is O(m*n) as each cell is processed once.
Example: For the grid [[0,0,0],[0,1,0],[0,0,0]], the output is 2, which is correct (two valid paths around the obstacle).
This solution handles all edge cases and provides an optimal way to compute the result.


作者声明:本文包含人工智能生成内容。