# Leetcode 63. Unique Paths II

## 題解

### 動態規劃

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # DFS
        # Time complexity: O(m*n)
        # Space complexity: O(m*n)
        m,n = len(obstacleGrid),len(obstacleGrid[0])
        grid = [[0] * n for i in range(m)]
        for y in range(m):
            if obstacleGrid[y][0] == 1:
                break
            grid[y][0] = 1
        for x in range(n):
            if obstacleGrid[0][x] == 1:
                break
            grid[0][x] = 1
        for y in range(1,m):
            for x in range(1,n):
                if obstacleGrid[y][x] == 0:
                    grid[y][x] = grid[y-1][x] + grid[y][x-1]
        return grid[m-1][n-1]

### 滾動數組

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # DFS
        # Time complexity: O(m*n)
        # Space complexity: O(m*n)
        m,n = len(obstacleGrid),len(obstacleGrid[0])
        grid = [0 for i in range(n)]
        grid[0] = 1 if obstacleGrid[0][0] == 0 else 0
        for y in range(m):
            for x in range(n):
                if obstacleGrid[y][x] == 1:
                    grid[x] = 0
                    continue
                if x - 1 >= 0 and obstacleGrid[y][x-1] == 0:
                    grid[x] += grid[x - 1]
        return grid[n-1]