unique_paths_ii.py

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        OBSTACLE, SPACE = 1, 0
        if obstacleGrid[0][0] == OBSTACLE:
            return 0

        rows, cols = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * cols for _ in range(rows)]
        dp[0][0] = 1

        for i in range(rows):
            for j in range(cols):
                if i == 0 and j == 0:
                    continue

                if obstacleGrid[i][j] == OBSTACLE:
                    dp[i][j] = 0 # no way to get there
                else:
                    from_top = dp[i - 1][j] if i > 0 else 0
                    from_left = dp[i][j - 1] if j > 0 else 0
                    dp[i][j] = from_top + from_left

        return dp[rows - 1][cols - 1]

        # Time Complexity: O(rows * cols)
        # Space Complexity: O(rows * cols)