• Home
  • home > theory > algorithm > leetcode >

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

    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笔记(16)：递推型动态规划——不同路径》,
    请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9142.html

    收藏
    上一篇：DP笔记(15)：递推型动态规划概念性总结
    下一篇：DP笔记(17)：DP键盘打印系列，2/4键键盘