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 detailed approach:
-
Dynamic Programming Table: We 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 the space complexity from O(m*n) to O(n). -
Initialization:
- The first cell (0,0) is initialized to 1 if it's not an obstacle, otherwise 0.
- The first row is filled by checking if each cell is an obstacle. If not, the number of ways to reach it is the same as the cell to its left (since we can only move right in the first row).
-
Filling the DP Array:
- For each subsequent row, we first check the first cell (j=0). If it's an obstacle, set
dp[0]to 0; otherwise, it retains the value from the previous row (since we can only move down to reach it). - For other cells in the row, if the cell is an obstacle, set
dp[j]to 0. Otherwise,dp[j]is the sum of the value from the cell above (currentdp[j]before update) and the cell to the left (dp[j-1]).
- For each subsequent row, we first check the first cell (j=0). If it's an obstacle, set
Solution Code
def uniquePathsWithObstacles(obstacleGrid):
m = len(obstacleGrid)
if m == 0:
return 0
n = len(obstacleGrid[0])
dp = [0] * n
# Initialize first cell
dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
# Fill first row
for j in range(1, n):
if obstacleGrid[0][j] == 1:
dp[j] = 0
else:
dp[j] = dp[j-1]
# 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 array instead of a 2D array saves space. Each entry in the array is updated in place as we process each row.
- Obstacle Handling: Obstacles are directly handled by setting the corresponding DP value to 0, as no paths can pass through an obstacle.
- Edge Cases: The code handles edge cases like empty grid, grid with obstacle at the start or end, and obstacles blocking entire rows or columns.
This approach efficiently computes the number of unique paths with a time complexity of O(m*n) and space complexity of O(n), where m is the number of rows and n is the number of columns in the grid.


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