Unique Paths II
Return the number of unique paths avoiding obstacles.
Examples
Input: [[0,0,0],[0,1,0],[0,0,0]]
Output:
Input: [[0,1],[0,0]]
Output:
Hints
Use dynamic programming where `dp[i][j]` represents the number of unique paths to reach cell `(i, j)` from the start, initializing `dp[0][0] = 1` if the start cell is not an obstacle.
For each cell `(i, j)`, if it's an obstacle (`obstacleGrid[i][j] == 1`), set `dp[i][j] = 0`. Otherwise, `dp[i][j] = dp[i-1][j] + dp[i][j-1]` (sum of paths from top and left cells).
Optimize space by using a 1D array (rolling array) to store only the current and previous row, reducing space complexity from O(mn) to O(n).
Related Problems
Unique Paths II
Return the number of unique paths avoiding obstacles.