Unique Paths II
You are given an m x n integer array grid. There are two possible moves from a cell (i, j): either to the cell below it at (i + 1, j), or to the cell to its right at (i, j + 1). You can only move either down or right at any point in time. Some cells may have obstacles, which are represented by the value 1 in the grid. Return the number of unique paths from the top-left cell to the bottom-right cell, or 0 if there is no such path.
Constraints:
- m == grid.length
- n == grid[0].length
- 1 <= m, n <= 100
- grid[i][j] is either 0 or 1
Examples:
Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There are two unique paths from the top-left cell to the bottom-right cell: down -> down -> right -> right and down -> right -> down -> right
Solutions
Dynamic Programming
We use dynamic programming to solve this problem. We create a 2D array dp where dp[i][j] represents the number of unique paths from the top-left cell to the cell at (i, j). We initialize dp[0][0] to 1 if the top-left cell is not an obstacle. Then we fill in the first row and the first column of dp. For each cell in the first row, if it is not an obstacle, we set dp[0][j] to dp[0][j - 1]. For each cell in the first column, if it is not an obstacle, we set dp[i][0] to dp[i - 1][0]. Then we fill in the rest of dp. For each cell, if it is not an obstacle, we set dp[i][j] to dp[i - 1][j] + dp[i][j - 1]. Finally, we return dp[m - 1][n - 1].
def uniquePathsWithObstacles(obstacleGrid):
m, n = len(obstacleGrid), len(obstacleGrid[0]); if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
return 0; dp = [[0] * n for _ in range(m)]; dp[0][0] = 1; for i in range(1, m):
if obstacleGrid[i][0] == 0:
dp[i][0] = dp[i - 1][0]; for j in range(1, n):
if obstacleGrid[0][j] == 0:
dp[0][j] = dp[0][j - 1]; for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[-1][-1]Follow-up:
What if we can move in all four directions (up, down, left, right) instead of just down and right?
