不同路径

题目描述

一个机器人位于一个 m x n 的网格的左上角。机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径可以到达终点？

解题步骤

为了计算到达终点的不同路径数，我们可以使用动态规划的思想来解决问题。

1. 定义状态：我们可以将问题转化为到达每个格子的不同路径数。令 dp[i][j] 表示到达网格第 i 行、第 j 列的格子的不同路径数。

2. 初始状态：根据题目的约束，机器人只能向下或向右移动，因此对于第一行和第一列的格子，机器人只能沿着一条路径到达。即 dp[i][0] = 1，dp[0][j] = 1。

3. 状态转移方程：对于其他格子，到达当前格子的不同路径数等于到达其上方格子的路径数加上到达其左方格子的路径数。因此，状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

4. 最终解：问题的解即为到达终点的不同路径数，即 dp[m-1][n-1]，其中 m 是网格的行数，n 是网格的列数。

下面是使用动态规划解决不同路径问题的算法框架：

function uniquePaths(m, n) {
  const dp = new Array(m);
  for (let i = 0; i < m; i++) {
    dp[i] = 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];
}