• home > theory > algorithm > leetcode >

    DP笔记(6):递推型动态规划——不同路径

    Author:zhoulujun Date:

    不同路径两题的考察点主要有以下几点:动态规划的思想和方法、状态定义和递推公式、边界条件的处理

    不同路径题目总结

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

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

    两题的考察点主要有以下几点:

    • 动态规划的思想和方法:两题都用到了动态规划来解决问题。动态规划是一种解决求解存在递推关系问题的有效方法,其基本思想是将原问题分解为多个子问题,并通过自底向上的方式求解子问题,最终得到原问题的解。

    • 状态定义和递推公式:两题都需要明确定义状态和递推公式。状态是用来描述子问题的解,递推公式是用来计算状态之间关系的公式。

    • 边界条件的处理:两题都需要处理边界条件。边界条件是指当子问题不存在时,状态的值是多少。

    不同路径

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

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

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

    动态规划:不同路径

    这道题目,刚一看最直观的想法就是用图论里的深搜,来枚举出来有多少种路径

    注意题目中说机器人每次只能向下或者向右移动一步,那么其实机器人走过的路径可以抽象为一颗二叉树,而叶子节点就是终点!

    如图举例:

    leetcode.不同路径

    此时问题就可以转化为求二叉树叶子节点的个数,代码如下:

    class Solution {
        dfs(i, j, m, n) {
            if (i > m || j > n) return 0; // 越界了
            if (i === m && j === n) return 1; // 找到一种方法,相当于找到了叶子节点
            return this.dfs(i + 1, j, m, n) + this.dfs(i, j + 1, m, n);
        }
    
        uniquePaths(m, n) {
            return this.dfs(1, 1, m, n);
        }
    }

    来分析一下时间复杂度,这个深搜的算法,其实就是要遍历整个二叉树。

    这棵树的深度其实就是m+n-1(深度按从1开始计算)。

    那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树(其实没有遍历整个满二叉树,只是近似而已)

    所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1),可以看出,这是指数级别的时间复杂度,是非常大的。


    数论方法

    从数学角度去看,这就是一个组合问题

    62.不同路径2 数论方法

    具体来说,机器人总共需要走 m−1 次向下和 n−1 次向右,总步数为 m+n−2。

    因此,我们需要从 m+n−2 步中选择 m−1 步向下或 n−1 步向右,这样路径的数量可以表示为组合数为image.png 即image.png

    var uniquePaths = function(m, n) {
      function factorial(num) {//用于计算给定数字的阶乘
        if (num === 0 || num === 1) return 1;
        let result = 1;
        for (let i = 2; i <= num; i++) {
          result *= i;
        }
        return result;
      }
    
      // Calculate C(m+n-2, m-1) or C(m+n-2, n-1)
      let numerator = factorial(m + n - 2);
      let denominator = factorial(m - 1) * factorial(n - 1);
    
      return numerator / denominator;
    };

    总的时间复杂度为 O(m+n−2)+O(m−1)+O(n−1),这等价于 O(m+n)。

    计算组合问题的代码还是有难度的,特别是处理溢出的情况!

    算法优化

    我们可以进一步优化代码,通过避免重复计算阶乘来减少复杂度。我们可以直接计算组合数 

    C(m+n−2,m−1) 或 C(m+n−2,n−1) 而无需计算完整的阶乘。

    var uniquePaths = function (m, n) {
    
      function combination(n, k) {// Helper function to calculate combination C(n, k)
        if (k > n - k) k = n - k;  // C(n, k) == C(n, n - k)
        let res = 1;
        for (let i = 0; i < k; i++) {
          res *= (n - i);
          res /= (i + 1);
        }
        return res;
      }
    
      return combination(m + n - 2, m - 1);
    };


    优化后的算法复复杂度
    1. combination函数的时间复杂度为 O(k),其中 k 是组合数公式中的较小值(即 k = Math.min(m-1, n-1))。

    2. 通过直接计算组合数,避免了重复计算阶乘,使得复杂度更加简化。

    因此,优化后的代码的时间复杂度为 O(min(m,n))。这是因为我们只需要计算较小值的阶乘,而不是整个范围的阶乘。

    这种优化不仅减少了计算时间,还避免了大数阶乘导致的潜在溢出问题,提高了代码的效率和可靠性。


    但是,数学方法在做题的时候不具备普适性(不一定想得到数学场景,想到了也不一定记得公式,记得公式代码也不一定优化得出来)


    动态规划

    利用动态规划算法

    解题思路

    以2*2的网格为例

    image.png

    • 从f[0][0]出发,那么开始时,节点f[0][0]=1

    • 节点f[0][1]只能由于f[0][0]向右移动得到,即 f[0][1]=f[0][0]

    • 节点f[1][0]同理,只能f[0][0]下移得到。即 f[1][0]=f[0][0]

    • 节点f[1][1],可以由于f[0][1]向下移动,f[1][0]向右移动。两种移动方式得到。即:f[1][1] = f[0][1] + f[1][0]

    • 最后,f[m-1][n-1],右下角的位置即为最终结果

    如果你还不理解的话,建议你手动画一下2*3的表格移动状态的转移过程。

    动规五部曲来分析:

    确定dp数组(dp table)以及下标的含义

    dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径,即:从[0] [0]出发走到[i] [j]有dp[i][j]种走法。

    确定递推公式

    想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。

    此时在回顾一下 dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。

    那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

    不同路径确定递推公式

    dp数组的初始化

    如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

    所以初始化代码为:

    const dp = Array.from({ length: m }, () => new Array(n).fill(0));
    for (let i = 0; i < m; i++) dp[i][0] = 1;
    for (let  j = 0; j < n; j++) dp[0][j] = 1;


    确定遍历顺序

    这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了

    这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

    举例推导dp数组

    62.不同路径1 举例推导dp数组

    function uniquePaths(m, n) {
      const dp = Array.from({ length: m }, () => new Array(n).fill(0));
      for (let i = 0; i < m; i++) dp[i][0] = 1;// 初始化第一列
      for (let j = 0; j < n; j++) dp[0][j] = 1;// 初始化第一行
      for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
      }
      return dp[m - 1][n - 1];
    }

    上面代码

    • 时间复杂度:O(m × n)

    • 空间复杂度:O(m × n)

    空间优化

    其实⽤⼀个⼀维数组(也可以理解是滚动数组)就可以了,但是不利于理解,可以优化点空间,建议先理解了⼆维,再理解⼀维,步骤如图:

    function uniquePaths(m, n) {
      const dp = new Array(n);
      for (let i = 0; i < n; i++)  dp[i] = 1;
      for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
          dp[j] += dp[j - 1];
        }
      }
      return dp[n - 1];
    }





    不同路径2

    这个题目是在上面的基础上,增加了障碍物,从而增加了题目的难度。

    示例 中的障碍物网格,obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]],那么就需要避开他!

    不同路径 II 障碍物

    上题我们已经详细分析了没有障碍的情况,有障碍的话,其实就是标记对应的dp table(dp数组)保持初始值(0)就可以了。

    递推公式中需要处理

    递推公式和62.不同路径一样,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

    因为有了障碍,(i, j)如果就是障碍的话应该就保持初始状态(初始状态为0)。

    不同路径2 dp数组手动推导

    所以代码为

    for (let i = 1; i < m; i++) {
      for (let j = 1; j < n; j++) {
        if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候,再推导dp[i][j]
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
      }
    }

    当然,更常见的写法

    for (let i = 1; i < m; i++) {
      for (let j = 1; j < n; j++) {
        if (obstacleGrid[i][j] === 1) {
          dp[i][j] = 0;
        } else {
          dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
      }
    }



    dp数组初始化需要的处理

    不同路径1,因为从(0, 0)的位置到(i, 0)的路径只有一条,所以dp[i][0]一定为1,dp[0][j]也同理。

    但如果(i, 0) 这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。

    63.不同路径II ,障碍之后(包括障碍)都是走不到的位置了

    下标(0, j)的初始化情况同理,所以本题初始化代码为:

    const dp = Array.from({ length: m }, () => new Array(n).fill(0));
    for (let i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
    for (let j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

    注意代码里for循环的终止条件,一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作,dp[0][j]同理

    上面代码其实就是:

    for (let i = 0; i < m; i++) {
      if (obstacleGrid[i][0] === 1) break;
      dp[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
      if (obstacleGrid[0][j] === 1) break;
      dp[0][j] = 1;
    }


    代码实现

    function uniquePathsWithObstacles(obstacleGrid) {
      if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) return 0;// 如果起始点就有障碍
      const m = obstacleGrid.length;
      const n = obstacleGrid[0].length;
      // dp数组中仍然是1可走,0不可走。不要与题目给的输入矩阵混淆
      const dp = Array.from({ length: m }, () => new Array(n).fill(0));
    
      for (let i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
      for (let j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
    
      for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
          if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候,再推导dp[i][j]
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
          }
        }
      }
    
      return dp[m - 1][n - 1];
    }


    空间优化

    function uniquePathsWithObstacles(obstacleGrid) {
      if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) return 0; // 如果起始点或终点有障碍物
      const m = obstacleGrid.length;
      const n = obstacleGrid[0].length;
     
      const dp = new Array(n).fill(0); // 使用一维数组来存储路径数
      dp[0] = 1; // 初始化起点
      
      for (let i = 0; i < m; i++) {// 填充 dp 数组
        for (let j = 0; j < n; j++) {
          if (obstacleGrid[i][j] === 1) {
            dp[j] = 0; // 有障碍物的地方路径数为 0
          } else if (j > 0) {
            dp[j] += dp[j - 1]; // 更新当前单元格的路径数
          }
        }
      }
      return dp[n - 1];
    }



    参考文章:

    一篇搞定动态规划之不同路径 https://www.51cto.com/article/684260.html

    https://programmercarl.com/0062.不同路径.html

    【LeetCode动态规划#02】图解不同路径I + II(首次涉及二维dp数组) https://www.cnblogs.com/DAYceng/p/17253288.html





    转载本站文章《DP笔记(6):递推型动态规划——不同路径》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9115.html