To solve this problem, we need to find the number of unique paths from the top-left corner to the bottom-right corner of a grid, avoiding obstacles. The solution uses dynamic programming with space optimization to efficiently compute the result.

Approach

The key insight is to use dynamic programming (DP) to keep track of the number of ways to reach each cell. We optimize space by using a 1D DP array instead of a 2D array since we only need the previous row's values and the current row's left values to compute the current cell's value.

1. Base Case: If the starting cell (0,0) is an obstacle, there are no paths, so return 0.
2. First Row: For the first row, each cell can only be reached from the left cell. If a cell is an obstacle, the number of ways to reach it is 0.
3. Subsequent Rows: For each subsequent row:
   • The first cell of the row can only be reached from the cell above it. If it's an obstacle, set the value to 0.
   • For other cells, if the cell is an obstacle, set the value to 0. Otherwise, the number of ways to reach it is the sum of the ways to reach the cell above it (from the previous row) and the cell to the left (from the current row).

Solution Code

def uniquePathsWithObstacles(obstacleGrid):
    if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0

    m = len(obstacleGrid)
    n = len(obstacleGrid[0])

    dp = [0] * n
    dp[0] = 1  # Starting point

    # 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]

    return dp[-1]

Explanation

• Space Optimization: The 1D DP array (dp) of size n (number of columns) is used to store the number of ways to reach each cell in the current row. This reduces the space complexity from O(m*n) to O(n).
• Time Complexity: O(m*n) since we traverse each cell exactly once.
• Edge Cases: Handles cases where the grid is empty, the starting cell is an obstacle, or the ending cell is an obstacle (since the DP array will return 0 if the ending cell is blocked).

This approach efficiently computes the number of unique paths while avoiding obstacles, making it suitable for large grids.

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