62. 不同路径 Medium
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
解题思路
输入：一个 m x n 的网格
输出：机器人从左上角出发，只能向下或向右移动，最终到达右下角的不同路径总数。
本题属于 动态规划 问题。
基本思路（二维 DP）
我们可以用二维数组 dp[i][j] 表示：到达第 i 行第 j 列时的路径数量。
初始化：
- 第一行和第一列都为 1，因为只能一直往右或往下一条路走到底。
状态转移方程：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]- 从上方格子走下来 + 从左边格子走过来。
答案： 返回
dp[m - 1][n - 1]。
空间优化（一维 DP）
注意到 dp[i][j] 只依赖于 当前行左边 和 上一行同列 的值，因此可以将二维数组压缩成一维数组。
状态转移方程：
dp[j] = dp[j] + dp[j - 1]dp[j]表示来自上方的路径数（上一行）。dp[j - 1]表示来自左边的路径数（当前行）。
答案： 返回
dp[n - 1]。
代码实现
python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 初始化dp数组，大小为n，所有元素初始为1
# dp数组表示从起点到每一列的路径数，因为在第一行只能向右走，所以所有列的初始路径数为1
dp = [1] * n
# 遍历每一行，从第二行开始更新dp数组
for i in range(1, m):
# 遍历每一列，从第二列开始更新每个格子的路径数
for j in range(1, n):
# 更新当前列的路径数，等于左边格子的路径数(dp[j-1])加上当前格子的路径数(dp[j])
dp[j] += dp[j-1]
# dp[-1]表示到达最后一列（右下角）的路径数
return dp[-1]
# 初始化dp数组，大小为m*n，所有元素初始为1
# dp[i][j] 表示从起点到达 (i, j) 的路径数
# 由于在第一行和第一列，机器人只能一直向右或向下移动，所以这些位置的路径数都为1
dp = [[1] * n for _ in range(m)]
# 填充dp数组，按照状态转移方程计算每个位置的路径数
# 从第二行和第二列开始更新路径数，因为第一行和第一列的路径数已经初始化为1
for i in range(1, m):
for j in range(1, n):
# 当前格子的路径数等于它上方格子(dp[i-1][j])和左边格子(dp[i][j-1])的路径数之和
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 返回到达右下角的路径数，即dp[m-1][n-1]
# 这是机器人从左上角 (0, 0) 到达右下角 (m-1, n-1) 的路径总数
return dp[m-1][n-1]
# 回溯的方案
memo = {}
def backtrack(i, j):
# 如果已经计算过当前位置的路径数，直接返回
if (i, j) in memo:
return memo[(i, j)]
# 到达右下角，找到一条路径
if i == m - 1 and j == n - 1:
return 1
# 到达最底行，只能往右走
if i == m - 1:
return backtrack(i, j + 1)
# 到达最右列，只能往下走
if j == n - 1:
return backtrack(i + 1, j)
# 递归计算右边和下边的路径数
memo[(i, j)] = backtrack(i, j + 1) + backtrack(i + 1, j)
return memo[(i, j)]
return backtrack(0, 0)javascript
/**
* 不同路径 - 二维 DP 解法
* @param {number} m 行数
* @param {number} n 列数
* @return {number} 不同路径的数量
*/
var uniquePaths = function(m, n) {
// 初始化 m 行 n 列的二维数组，全部填 1
// 因为第一行和第一列只有一种走法（一直往右 or 一直往下）
const dp = Array.from({ length: m }, () => Array(n).fill(1));
// 从第 2 行、第 2 列开始计算
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];
};
/**
* 不同路径 - 一维 DP 优化
* @param {number} m 行数
* @param {number} n 列数
* @return {number} 不同路径的数量
*/
var uniquePaths = function(m, n) {
// 初始化一维数组，第一行只有 1 种走法
const dp = Array(n).fill(1);
// 从第 2 行开始计算
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// dp[j] 原来存的是上一行的值（来自上方）
// dp[j-1] 是当前行左边格子的值（来自左方）
dp[j] += dp[j - 1];
}
}
// 最右下角的路径数
return dp[n - 1];
};复杂度分析
时间复杂度：O(m * n)
空间复杂度：O(n)