Unique Paths II

Problem Id: 63 Difficulty: Medium Tag: Array Tag: Dynamic Programming


Intuition

This is almost the same as <62. Unique Path>.

For node x, y without obstacle, the number of ways to get to it is the number of ways to get to x - 1, y plus the number of ways to get to x, y - 1.

For node x, y with obstacle, the number of ways to get to it is zero.

Solution


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or not obstacleGrid[0]:
            return 0

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [0] * n
        dp[0] = 1

        for i in range(m):
            if obstacleGrid[i][0] == 1:
                dp[0] = 0
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                else:
                    dp[j] += dp[j - 1]
        return dp[-1]