题目大意:从一个\(m \times n\)的有障碍物的格子上左上角走到右下角,只能向右或者向下走,总共有多少种不同的走法?
63题和62题很相似,只是格子有障碍物。解决的办法是如果有障碍物,那么那个格子的可行办法是0.
使用递推(动态规划)的办法:
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
self.grid = obstacleGrid
m = len(obstacleGrid)
n = len(obstacleGrid[0])
self.f = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
self.f[1][1] = 1 if obstacleGrid[0][0] == 0 else 0
def dp(y, x):
for y in range(1, m + 1):
for x in range(1, n + 1):
if y == 1 and x == 1:
continue
elif self.grid[y - 1][x - 1] == 1:
self.f[y][x] = 0
else:
self.f[y][x] = self.f[y - 1][x] + self.f[y][x - 1]
dp(m + 1, n + 1)
return self.f[m][n]