Unique Paths 2

Related: Unique Paths

Intuition

• This problem is the same with the Memoization format, but you simply choose not to go down the DFS paths that have an obstacle (return 0 when out of bounds or when you reach an obstacle).
• Note that the difference between this problem and Unique Paths is you have to be careful about pre-initializing the array, since if there is a blocker on the last row or last column, then the previous values are also blocked, since you can only go down on the last column and can only go to the right on the last row.
• So with the 1D DP method, we do the same thing by setting that DP index to 0, thereby making that entire set of subproblems handled.

Runtime

• Same as Unique Paths, with $O(mn)$ runtime and $O(n)$ space with the 1D DP version.

Code

1D DP

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        M, N = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * N
        dp[-1] = 1
        for r in reversed(range(M)):
            for c in reversed(range(N)):
                if obstacleGrid[r][c] == 1:
                    dp[c] = 0
                elif c < N - 1:
                    dp[c] = dp[c] + dp[c + 1]
 
        return dp[0]

Tabulation DP

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[-1][-1] == 1:
            return 0
            
        m, n = len(obstacleGrid), len(obstacleGrid[0])
       
        nums = []
        for i in range(m - 1):
            nums.append([0] * (n - 1) + [1])
        nums.append([1] * n)
 
        is_blocked = False
        for i in range(n - 1, -1, -1):
            if obstacleGrid[-1][i] == 1:
                is_blocked = True
            if is_blocked:
                nums[-1][i] = 0
                
        is_blocked = False
        for j in range(m - 1, -1, -1):
            if obstacleGrid[j][-1] == 1:
                is_blocked = True
            if is_blocked:
                nums[j][-1] = 0
 
        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                if obstacleGrid[i][j] == 1:
                    nums[i][j] = 0
                else:
                    nums[i][j] = nums[i + 1][j] + nums[i][j + 1]
        
        return nums[0][0]

Memoization

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = {}
        def dfs(row, col):
            if row >= m or col >= n or obstacleGrid[row][col] == 1:
                return 0
            if row == m - 1 and col == n - 1:
                return 1
            if (row, col) in dp:
                return dp[(row, col)]
            dp[(row, col)] = dfs(row + 1, col) + dfs(row, col + 1)
            return dp[(row, col)]
        
        return dfs(0, 0)

Notes

---

References