Posted on 2023-08-12 16:56
Uriel 阅读(26)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
给出一个二维矩阵，0可以走，1代表障碍，每次可以向右或者向下走，输出从左上角到右下角一共多少条路线，DP
1 #63
2 #Runtime: 27 ms (Beats 59.11%)
3 #Memory: 13.3 MB (Beats 82.78%)
4
5 class Solution(object):
6 def uniquePathsWithObstacles(self, obstacleGrid):
7 """
8 :type obstacleGrid: List[List[int]]
9 :rtype: int
10 """
11 n, m = len(obstacleGrid), len(obstacleGrid[0])
12 dp = [[0] * m for _ in range(n)]
13 for i in range(n):
14 if obstacleGrid[i][0] == 0:
15 dp[i][0] = 1
16 else:
17 break
18 for i in range(m):
19 if obstacleGrid[0][i] == 0:
20 dp[0][i] = 1
21 else:
22 break
23 for i in range(1, n):
24 for j in range(1, m):
25 if obstacleGrid[i][j] == 0:
26 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
27 return dp[-1][-1]