Skip to main content

63. Unique Paths II

Python​

DFS with cache​

from functools import cache


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])

        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0

        @cache
        def dfs(row, col):
            if row == m-1 and col == n-1:
                if path or obstacleGrid[row][col] == 0:
                    return 1
                else:
                    return 0

            down_reachable, right_reachable = 0, 0
            if row + 1 < m and obstacleGrid[row+1][col] == 0:
                down_reachable = dfs(row+1, col)

            if col + 1 < n and obstacleGrid[row][col+1] == 0:
                right_reachable = dfs(row, col+1)

            return down_reachable + right_reachable

        result = dfs(0, 0)

        return result