不同路径#

题目#

有一个机器人位于一个 m * n 网格的左上角，网格的起始坐标为 [0,0] ，机器人每次只能向右或者向下移动。机器人想要到达网格的右下角（网格坐标 [m−1,n−1]）。

请问：机器人从左上角移动到右下角，一共有 多少种不同的路径 ？

示例

若 m=3,n=2，网格如下：
(0,0) -> (0,1)
↓        ↓
(1,0) -> (1,1)
↓        ↓
(2,0) -> (2,1)
机器人要从 (0,0) 走到 (2,1)。可能的路径举例：

右 -> 下 -> 下

下 -> 下 -> 右

下 -> 右 -> 下

具体计算后可得共有 3 条路径。

解题思路

机器人想要到达(i, j) 这个坐标，要么是从上面下来(i-1, j)，要么是从左边过来(i, j-1)，也就是说：

到达(i, j) 路径数 = 到达(i-1, j)路径数 + 到达(i, j-1)路径数

动态规划三个特点：

最优子结构 ✅
重叠子问题 ✅
存储子问题的解 ✅

寻找状态转移的方程

初始条件：
- 对于第一行的格子(0, j)，机器人只能从左到右抵达，因此路径只有一条：
  $dp[0][j]=1$
- 对于第一列的格子(i, 0)，机器人只能从上往下抵达，因此路径只有一条：
  $dp[i][0] = 1$
状态转移方程
$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

代码实现

表格法（自底向上）

/**
 * 不同路径：计算从左上角 (0,0) 到右下角 (m-1,n-1) 有多少种不同的路径
 * @param {number} m - 网格行数
 * @param {number} n - 网格列数
 * @return {number} - 不同路径的总数
 */
function uniquePaths(m, n) {
  // 1. 先创建一个 dp 数组，也就是表格，用于缓存数据
  const dp = Array.from({ length: m }, () => new Array(n).fill(null))

  // 2. 初始化第一行
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1
  }

  // 3. 初始化第一列
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1
  }

  // 4. 填表，一边填表一边计算需要多少条路径
  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]
}

记忆化搜索（自上而下）

/**
 * 不同路径：计算从左上角 (0,0) 到右下角 (m-1,n-1) 有多少种不同的路径
 * @param {number} m - 网格行数
 * @param {number} n - 网格列数
 * @return {number} - 不同路径的总数
 */
function uniquePaths(m, n) {
  // 1. 先创建一个 dp 数组，也就是表格，用于缓存数据
  const dp = Array.from({ length: m }, () => new Array(n).fill(null))

  function helper(i, j) {
    // 边界的处理
    if (i < 0 || j < 0) return 0

    // 起点，满足以下条件，说明要么是第一行，要么是第一列
    if (i === 0 || j === 0) return 1

    if (dp[i][j] !== null) return dp[i][j]

    // 代码走到这一步，说明没有，我们需要递归计算，并且在计算的时候缓存结果
    dp[i][j] = helper(i - 1, j) + helper(i, j - 1)
    return dp[i][j]
  }

  return helper(m - 1, n - 1)
}

可以去做算法的变量追踪。

-EOF-