当前位置:   article > 正文

代码随想录算法训练营Day39 | 62. 不同路径 | 63. 不同路径 II

代码随想录算法训练营Day39 | 62. 不同路径 | 63. 不同路径 II

62. 不同路径

题目链接| 理论基础

  1. dp 数组下标的含义:dp[i][j] 是到达位置 (i, j) 的不同路径数
  2. dp 递推公式:dp[i][j] = dp[i-1][j] + dp[i][j-1],想要到达 (i, j) 只有两种方法
    • 先到达 (i-1, j),然后向右移动
    • 先到达 (i, j-1),然后向下移动
  3. dp 数组的初始化:对于任意合法的 i, jdp[i][0] = 1, dp[0][j] = 1,其余位置均为 0(无所谓初始化为多少)
    • 到达第一行和第一列的任意位置都只有一种方法
  4. 遍历顺序:从左到右、从上到下递推即可,保证使用 dp 公式的时候之前的值已经计算过
  5. 举例推导 dp 数组:省略
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # dp[i][j] represents the number of ways to reach the position (i, j)
        dp = [[0 for j in range(n)] for i in range(m)]

        # initialization: all positions in the first row and column can be reached uniquely
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        # dp formula
        # since it can only go down or right, either iteration over row or column first can work
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

拓展

本题可以用数论直接分析出结果:对于 m × n m\times n m×n 的网格,必然需要 m + n − 2 m+n-2 m+n2 步,其中有 m − 1 m-1 m1 步是向下走的,所以所有路径的总数是 C m + n − 2 m − 1 \mathcal{C}_{m+n-2}^{m-1} Cm+n2m1
要注意,计算组合的时候不能直接计算分子、分母然后相除,而是要在计算分子时不断除以分母,防止溢出。

另外,图论中的深度搜索似乎也可以完成:将路径看成二叉树的话,遍历所有的叶子节点即可。然而这棵树的深度是 m + n − 1 m+n-1 m+n1,意味着复杂度是 O ( 2 m + n ) O(2^{m+n}) O(2m+n),所以会直接超时,因为其中绝大部分的遍历都是没有意义的。

63. 不同路径 II

题目链接 | 理论基础

  1. dp 数组下标的含义:dp[i][j] 是到达位置 (i, j) 的不同路径数
  2. dp 递推公式:if obstacleGrid[i][j] == 0: dp[i][j] = dp[i-1][j] + dp[i][j-1],想要到达 (i, j) 只有两种方法(如果当前位置没有障碍的话)
    • 先到达 (i-1, j),然后向右移动
    • 先到达 (i, j-1),然后向下移动
  3. dp 数组的初始化:上一题中对于任意合法的 i, jdp[i][0] = 1, dp[0][j] = 1,其余位置均为 0;本题中,如果行/列中存在一个障碍,则障碍之后的所有位置都都应该初始化为 0(无法到达)
    • 到达第一行和第一列的任意位置都只有一种方法
  4. 遍历顺序:从左到右、从上到下递推即可,保证使用 dp 公式的时候之前的值已经计算过
  5. 举例推导 dp 数组:省略
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        # dp[i][j] represents the number of ways to reach position (i, j)
        # if the position (i, j) has an obstacle, there is 0 way to reach this position
        dp = [[0 for i in range(n)] for j in range(m)]

        # initialization: all positions in the first row and column can be reached uniquely
        for i in range(m):
            if obstacleGrid[i][0] or (i > 0 and dp[i-1][0] == 0):
                dp[i][0] = 0
            else:
                dp[i][0] = 1
        for j in range(n):
            if obstacleGrid[0][j] or (j > 0 and dp[0][j-1] == 0):
                dp[0][j] = 0
            else:
                dp[0][j] = 1
        
        # dp formula
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j]:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-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

本题的初始化中,“障碍之后的位置无法到达”也是个坑。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/212006
推荐阅读
相关标签
  

闽ICP备14008679号