题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个二维数组，其中的 0 和 1 分别代表空和障碍物，求从该数组的左上角移动到右下角的所有路径数目。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 一维数组
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        f = [0]*(n+1)
        f[1] = 1
        for i in range(m):
            for j in range(n):
                # print(f)
                if obstacleGrid[i][j] == 1:
                    f[j+1] = 0
                else:
                    f[j+1] = f[j] + f[j+1]
        return f[n]
        # 二维数组
        # m = len(obstacleGrid)
        # n = len(obstacleGrid[0])
        # f = [[0]*(n+1) for _ in range(m+1)]
        # f[0][1] = 1
        # for i in range(m):
        #     for j in range(n):
        #         if obstacleGrid[i][j] == 1:
        #             f[i+1][j+1] = 0
        #         else:
        #             f[i+1][j+1] = f[i+1][j] + f[i][j+1]
        # return f[m][n]