63. Unique Paths II刷题笔记

问题描述 主要是稀奇古怪的边界条件，例如左上角是1，最左边和最上边是1，有多个1，输入为行，或者列

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [0]*m
        if obstacleGrid[0][0]:
            return 0
        dp[0] = 1
        for i in range(1,m):
            if obstacleGrid[i][0]:
                dp[i] = 0
            else:
                dp[i] = dp[i-1]
            
        
        for i in range(1,n):
            if obstacleGrid[0][i]:
                dp[0] = 0
            for j in range(1,m):
                if obstacleGrid[j][i]:
                    dp[j] = 0
                else:
                    dp[j]+=dp[j-1]
        return dp[m-1]

运行结果：

在第一列的初始化用上break，速度大大提升

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [0]*m
        if obstacleGrid[0][0]:
            return 0
        dp[0] = 1
        for i in range(1,m):
            if obstacleGrid[i][0]:
                break
            else:
                dp[i] = 1               
            
        
        for i in range(1,n):
            if obstacleGrid[0][i]:
                dp[0] = 0
            for j in range(1,m):
                if obstacleGrid[j][i]:
                    dp[j] = 0
                else:
                    dp[j]+=dp[j-1]
        return dp[m-1]