Jianbo Dai's

lc063.不同路径II

 
  • Mar 26, 2021

题目链接

相比于lc062来说在网格中又加入了障碍物。只要处理好第一行和第一列的情况，就比较好做了，在有障碍物的时候把相应位置的方案数清零。这个算法的时间复杂度是O（N），空间复杂度是O（N）。

python:

class Solution:
    def uniquePathsWithObstacles1(self, obstacleGrid: List[List[int]]) -> int:
        rows, cols = len(obstacleGrid), len(obstacleGrid[0])
        if rows == 0:
            return 0
        dp = [1]*cols
        for i in range(rows):
            for j in range(cols):
                if obstacleGrid[i][j] == 0:
                    if i == 0:
                        dp[j] = dp[j-1]
                    elif j == 0:
                        continue
                    else:
                        dp[j] += dp[j-1]
                else:
                    dp[j] = 0
        return dp[-1]
		
    def uniquePathsWithObstacles2(self, obstacleGrid: List[List[int]]) -> int:
        rows, cols = len(obstacleGrid), len(obstacleGrid[0])
        if rows == 0:
            return 0
        dp = [[1]*cols for _ in range(rows)]
        for i in range(rows):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = 0
        for j in range(cols):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j-1]
            else:
                dp[0][j] = 0
        for i in range(1, rows):
            for j in range(1, cols):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = 0

        return dp[-1][-1]
		
    def uniquePathsWithObstacles3(self, obstacleGrid: List[List[int]]) -> int:
        rows, cols = len(obstacleGrid), len(obstacleGrid[0])
        if rows == 0:
            return 0
        dp = [[1]*cols for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                if obstacleGrid[i][j] == 0:
                    if i == 0:
                        dp[0][j] = dp[0][j-1]
                    elif j == 0:
                        dp[i][0] = dp[i-1][0]
                    else:
                        dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = 0
        return dp[-1][-1]
Search