LeetCode:63. 不同路径 II(python)

LeetCode:63. 不同路径 II(python)

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

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

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

LeetCode:63. 不同路径 II(python)

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明:m 和 n 的值均不超过 100。

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

LeetCode 链接


思路:

  1. 递归(超时),递归遍历图的轨迹:从当前坐标的向右走的情况 + 从当前坐标向下走的情况
    • 若当前位置超出边界或遇到障碍,则该路径失效,返回 0;
    • 若当前位置到达目的地,且目的地有效(不为 1),则返回 1。
  2. 记忆递归,添加记忆字典{(坐标):当前坐标路径数}
  3. 动态规划
    • 状态:图中位置,即每一处坐标,dp 数组表示当前位置的路径数。
    • 选择
      • 当前位置不为障碍物时,当前位置的路径数为其向左位置和向右位置的路径数之和;
      • 当前位置为障碍物时,当前位置的路径数为 0(不通)。
    • 初始化
      • dp数组维度为 m×n(图的维度),值为 0,表示路径数初始为 0
      • 从坐标 (0, 0) 处位置一直向右走,若未遇到障碍物,则将 dp 值设为 1,表示有一条路径可达当前位置;若遇到障碍物,则跳出,表示当前位置不可达,路径数为 0,且其后的向右位置亦不可达。
      • 从坐标 (0, 0) 处位置一直向下走(同上),若未遇到障碍物,则将 dp 值设为 1,表示有一条路径可达当前位置;若遇到障碍物,则跳出,表示当前位置不可达,路径数为 0,且其后的向下位置亦不可达。
    • 返回值:目的地的路径数 dp[m-1][n-1]
  4. 优化空间的动态规划,将图作为动态转移数组,节省空间。

附代码1(Python3):递归(超时)

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid:
            return 0
        return self.recurve(0, 0, obstacleGrid)
    
    def recurve(self, x, y, obstacleGrid):
        if x==len(obstacleGrid) or y==len(obstacleGrid[0]) or obstacleGrid[x][y]==1:              # 坐标超边界,或遇障碍物
            return 0
        if x==len(obstacleGrid)-1 and y==len(obstacleGrid[0])-1 and obstacleGrid[x][y]!=1:    # 到达目的地,且目的地可达
            return 1
        return self.recurve(x+1, y, obstacleGrid)+self.recurve(x, y+1, obstacleGrid)              # 递归向右走和向下走的情况
test = Solution()
obstacleGrid_li = [[[0,0,0],
                    [0,1,0],
                    [0,0,0]],
                   [[0,0],
                    [1,1],
                    [0,0]]
                  ]
for obstacleGrid in obstacleGrid_li:
    print(test.uniquePathsWithObstacles(obstacleGrid))
2
0

附代码2(Python3):记忆递归

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid:
            return 0
        memo = {}            # 记忆
        return self.memo_recurve(0, 0, obstacleGrid, memo)
    
    def memo_recurve(self, x, y, obstacleGrid, memo):
        if (x,y) in memo:
            return memo[(x,y)]
        
        if x==len(obstacleGrid) or y==len(obstacleGrid[0]) or obstacleGrid[x][y]==1:
            memo[(x,y)] = 0
            return memo[(x,y)]
        
        if x==len(obstacleGrid)-1 and y==len(obstacleGrid[0])-1 and obstacleGrid[x][y]!=1:
            memo[(x,y)] = 1
            return memo[(x,y)]
        
        memo[(x,y)] = self.memo_recurve(x+1, y, obstacleGrid, memo)+self.memo_recurve(x, y+1, obstacleGrid, memo)
        return memo[(x,y)]
test = Solution()
obstacleGrid_li = [[[0,0,0],
                    [0,1,0],
                    [0,0,0]],
                   [[0,0],
                    [1,1],
                    [0,0]]
                  ]
for obstacleGrid in obstacleGrid_li:
    print(test.uniquePathsWithObstacles(obstacleGrid))
2
0

附代码3(Python3):动态规划

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        # 初始化 dp 数组
        dp = [[0]*(n) for _ in range(m)]
        for i in range(m):              # 初始化 dp 数组的第 0 列
            if obstacleGrid[i][0]==0:
                dp[i][0] = 1
            else:
                break
        for j in range(n):              # 初始化 dp 数组的第 0 行
            if obstacleGrid[0][j]==0:
                dp[0][j] = 1
            else:
                break
        # 动态转移
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j]!=1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = 0
        return dp[m-1][n-1]
test = Solution()
obstacleGrid_li = [[[0,0,0],
                    [0,1,0],
                    [0,0,0]],
                   [[0,0],
                    [1,1],
                    [0,0]]
                  ]
for obstacleGrid in obstacleGrid_li:
    print(test.uniquePathsWithObstacles(obstacleGrid))
2
0

附代码4(Python3):优化空间的动态规划

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid or obstacleGrid[0][0]==1:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        # 初始化 obstacleGrid 为 动态转移数组
        path_flag = True
        for i in range(m):              # 初始化 dp 数组的第 0 列
            if path_flag and obstacleGrid[i][0]==0:
                obstacleGrid[i][0] = 1
            else:
                path_flag = False
                obstacleGrid[i][0] = 0
        path_flag = True
        for j in range(1, n):           # 初始化 dp 数组的第 0 行
            if path_flag and obstacleGrid[0][j]==0:
                obstacleGrid[0][j] = 1
            else:
                path_flag = False
                obstacleGrid[0][j] = 0
        # 动态转移
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j]!=1:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
                else:
                    obstacleGrid[i][j] = 0
        return obstacleGrid[m-1][n-1]
test = Solution()
obstacleGrid_li = [[[0,0,0],
                    [0,1,0],
                    [0,0,0]],
                   [[0,0],
                    [1,1],
                    [0,0]]
                  ]
for obstacleGrid in obstacleGrid_li:
    print(test.uniquePathsWithObstacles(obstacleGrid))
2
0
上一篇:luoogu 3812


下一篇:【Offer】[63] 【股票的最大利润】