LeetCode 63. [Python] Unique Paths II
原题链接
中等
作者:
徐辰潇
,
2021-02-04 01:07:03
,
所有人可见
,
阅读 368
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
#Simple dp
#TC: O(mn)
#SC: O(n)
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [0]*n
dp[0] = 1 - obstacleGrid[0][0]
for i in range(1,n):
dp[i] = dp[i-1]*(1-obstacleGrid[0][i])
for i in range(1, m):
dp[0] = dp[0]*(1-obstacleGrid[i][0])
for j in range(1, n):
dp[j] = (dp[j] + dp[j-1])*(1-obstacleGrid[i][j])
return dp[-1]