[LeetCode] 63. Unique Paths II

Problem :  https://leetcode.com/problems/unique-paths-ii/

Similar to the 62 Unique Paths

Time Complexity : O ( M * N )

Space Complexity : O (M * N )

from functools import lru_cache

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        @lru_cache(maxsize = None)
        def paths(i, j):
            if i < 0 or j < 0:
                return 0
            
            if obstacleGrid[i][j] == 1:
                return 0
            
            # 1 step to start from the top-left cell
            if i == 0 and j == 0:
                return 1
            
            return paths(i-1, j) + paths(i, j-1)
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        return paths(m-1, n-1)

A bottom-up DP solution.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        ROW = len(obstacleGrid)
        COLUMN = len(obstacleGrid[0])
        
        dp = [[0] * (COLUMN+1) for _ in range(ROW+1)]
        
        dp[ROW-1][COLUMN-1] = 1 if obstacleGrid[ROW-1][COLUMN-1] != 1 else 0
        
        for y in reversed(range(ROW)):
            for x in reversed(range(COLUMN)):
                if y == ROW-1 and x == COLUMN-1:
                    continue
                    
                if obstacleGrid[y][x] == 1:
                    continue
                
              	
                dp[y][x] = dp[y+1][x] + dp[y][x+1]
                
        return dp[0][0]

Edited on 04/28/2021. Add the DP solution.