63. Unique Paths II

Summary

Return how many unique paths a robot can take from the top-left to the bottom-right corner while staying within the grid. Each cell in the grid is either open (0) or blocked by an obstacle (1), and the robot may not step on obstacle cells.

Approach

Use dynamic programming. The number of paths to cell (i, j) equals the paths reaching the cell above plus the paths reaching the cell to the left. Cells that contain obstacles contribute zero paths and block any further traversal through that square.

Function

Initialization:

dp: m x n grid.

For each cell (i, j) in obstacleGrid:

if obstacleGrid[i][j] == 1:
    dp[i][j] = 0
else if i == 0 and j == 0:
    dp[i][j] = 1
else:
    paths = 0
    if i > 0:
        paths += dp[i-1][j]
    if j > 0:
        paths += dp[i][j-1]
    dp[i][j] = paths
return dp[m-1][n-1]

Complexity

Time Complexity: O(MN) Space Complexity: O(MN)