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 blocked (obstacles).
Approach
The problem can be efficiently solved using Dynamic Programming (DP) with space optimization. Here's the step-by-step approach:
-
Initialization:
- If the grid is empty or the starting cell (0,0) is blocked, return 0 immediately.
- Use a 1D DP array where
dp[j]represents the number of ways to reach the j-th cell in the current row. This reduces space complexity from O(m*n) to O(n).
-
First Row:
- For the first row, each cell can only be reached from the left. If a cell is blocked, all subsequent cells in the row are unreachable.
-
Subsequent Rows:
- For each row, update the DP array:
- The first cell of the row is reachable only if it's not blocked and the cell above it (from the previous row) was reachable.
- For other cells, if the cell is not blocked, the number of ways to reach it is the sum of ways to reach the cell above (from the previous row's DP value) and the cell to the left (current row's DP value).
- 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 # Starting 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
# Update other columns
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[j] = 0
else:
dp[j] += dp[j-1]
return dp[-1]
Explanation
- Space Optimization: Using a 1D DP array allows us to reuse space for each row, making the solution memory efficient.
- Edge Cases: Handles blocked starting/ending cells, empty grids, and 1x1 grids correctly.
- Efficiency: Time complexity is O(m*n) (each cell is processed once), and space complexity is O(n) (size of the DP array).
This approach ensures we compute the number of unique paths efficiently while considering obstacles in the grid. The DP array is updated row by row, leveraging previous results to avoid redundant calculations.


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