63. Unique Paths II
Array, DP, Matrix ·Problem Statement
link: https://leetcode.com/problems/unique-paths-ii/ https://leetcode.cn/problems/unique-paths-ii/
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109.
Example:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Solution Approach
Use dynamic programming to calculate unique paths from the top-left to each cell in the obstacleGrid, while accounting for obstacles.
Algorithm
- Initialization: Return 0 if start or end point is an obstacle; otherwise, set start to 1.
- First Row & Column: Set values based on the presence of obstacles and their predecessors.
- DP Calculation: For each subsequent cell, if not an obstacle, set its value as the sum of its top and left neighbors. Return the bottom-right cell’s value.
Implement
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid[0])
if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
return 0
obstacleGrid[0][0] = 1
for i in range(1, m):
obstacleGrid[i][0] = 0 if obstacleGrid[i][0] else obstacleGrid[i - 1][0]
for i in range(1, n):
obstacleGrid[0][i] = 0 if obstacleGrid[0][i] else obstacleGrid[0][i - 1]
for i in range(1, m):
for j in range(1, n):
obstacleGrid[i][j] = 0 if obstacleGrid[i][j] else obstacleGrid[i][j - 1] + obstacleGrid[i - 1][j]
return obstacleGrid[m - 1][n - 1]