leetcode 不同路径

1.不同路径I

https://leetcode.cn/problems/unique-paths/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

1.排列组合法

总步数只可能是m+n-2步，最终到达终点。其实m-1步向下，n-1步向右。自然可以看作是一个组合问题，从m+n-2中选择m-1个位置，让机器人向下，其他n-1位置向右。答案为$C_{m+n-2}^{m-1}$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):

    @staticmethod
    def factorial(n):
        res = 1
        for i in range(1,n+1):
            res *= i
        return res

    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return self.factorial(m+n-2) // (self.factorial(m-1) * self.factorial(n-1))

2.动态规划

任何一个格子只能从左边或者上方到达，因此有nums[i][j] = nums[i-1][j] + nums[i][j-1]。同时只需要使用额外O(n)的内存，不需要使用O(m*n)或者O(2n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        cur = [1] * n
        for _ in range(m-1): # for the rest m-1 rows
            for j in range(n):
                if j != 0:
                    cur[j] = cur[j-1] + cur[j] # save space, use one row
        return cur[-1]

2. 不同路径II

https://leetcode.cn/problems/unique-paths-ii/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

1. 错误的做法：递归

思想是：一个点到终点的路径数等于右边到终点的路径数加上下边到终点的路径数。比较直观。但是递归过程中会有大量的重复运算。比如找self.helper(obstacleGrid, i+1, j, row_len, col_len)和self.helper(obstacleGrid, i, j+1, row_len, col_len)会重复计算重合的长方形，导致超出时间限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 超出时间限制🚫
class Solution(object):
    def helper(self, obstacleGrid, i, j, row_len, col_len):
        res = 0
        if obstacleGrid[i][j] == 1:
            return res
        if i == row_len - 1 and j == col_len - 1:
            return 1
        if i < row_len - 1:
            res += self.helper(obstacleGrid, i+1, j, row_len, col_len)
        if j < col_len - 1:
            res += self.helper(obstacleGrid, i, j+1, row_len, col_len)
        return res

    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        return self.helper(obstacleGrid, 0, 0, len(obstacleGrid), len(obstacleGrid[0]))

2. 动态规划

类似于上一题的做法，只是需要额外判断一个点是否是障碍物。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 空间复杂度O(m*n)
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        res = [
            [0 for _ in col] for col in obstacleGrid
        ]
        for i in range(len(obstacleGrid)):
            for j in range(len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 1:
                    res[i][j] = 0
                    continue
                if i == 0 and j == 0:
                    res[i][j] = 1
                elif i == 0:
                    res[i][j] = res[i][j-1]
                elif j == 0:
                    res[i][j] = res[i-1][j]
                else:
                    res[i][j] = res[i][j-1] + res[i-1][j]
        return res[-1][-1]

优化空间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        res = [0 for _ in range(len(obstacleGrid[0]))]
        for i in range(len(obstacleGrid)):
            for j in range(len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 1:
                    res[j] = 0
                    continue
                if i == 0:
                    if j == 0:
                        res[j] = 1
                    else:
                        res[j] = res[j-1]
                else:
                    if j != 0:
                        res[j] = res[j-1] + res[j]
        return res[-1]

3. 不同路径III

https://leetcode.cn/problems/unique-paths-iii/

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
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
28
29
30
31
32
33
34
35
36
class Solution(object):
    def helper(self, grid, cur, steps):
        if cur[0] < 0 or cur[0] >= self.row_len or cur[1] < 0 or cur[1] >= self.col_len:
            return
        if grid[cur[0]][cur[1]] == 2:
            self.res += (steps == self.steps)
        elif grid[cur[0]][cur[1]] == 0:
            grid[cur[0]][cur[1]] = -1
            # up
            self.helper(grid, [cur[0]-1, cur[1]], steps+1)
            # down
            self.helper(grid, [cur[0]+1, cur[1]], steps+1)
            # left
            self.helper(grid, [cur[0], cur[1]-1], steps+1)
            # right
            self.helper(grid, [cur[0], cur[1]+1], steps+1)
            grid[cur[0]][cur[1]] = 0

    def uniquePathsIII(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        self.steps = 1 # attention
        self.row_len = len(grid)
        self.col_len = len(grid[0])
        for i in range(self.row_len):
            for j in range(self.col_len):
                if grid[i][j] == 0:
                    self.steps += 1
                elif grid[i][j] == 1:
                    cur = [i, j]
                    grid[i][j] = 0
        self.res = 0
        self.helper(grid, cur, 0)
        return self.res
leetcode
leetcode-动态规划

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！