62. 不同路径 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/unique-paths/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start”）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
提示：
- 1 <= m, n <= 100
- 题目数据保证答案在 32 位整数范围内
题目详细分析
- 数据范围：m, n <= 100，结果在 32 位整数范围内（实际约 C(198,99) ≈ 9e55 会溢出 32 位，但题目保证不溢出）。
- 核心约束：只能向右或向下，不能向左或向上（无回溯）。
- 边界条件：第一行所有格子只有一条路径（一直向右）；第一列所有格子只有一条路径（一直向下）。
- 隐藏条件：本质是一个组合数学问题——一共需要走 (m-1)+(n-1) = m+n-2 步，其中选择 n-1 步向右（或 m-1 步向下），所以答案是 C(m+n-2, n-1)。
小白版直白理解
你站在一个棋盘左上角，想走到右下角，每次只能往右或往下走一格。问有多少种不同的走法？这就像你每天从家走到公司，只能往东或往南走，问有多少条不同的路线。你到达某个路口的方法数 = 到达它左边路口的方法数 + 到达它上面路口的方法数，因为从左边过来或者从上面过来都行。
解题思路
思路一：二维 DP（推荐）
核心洞察：到达 (i,j) 的路径数 = 到达 (i-1,j) 的路径数（从上面来）+ 到达 (i,j-1) 的路径数（从左边来）。第一行和第一列的所有格子都只有 1 条路径。
DP 五步法：
- dp 定义：
dp[i][j]表示到达 (i,j) 的不同路径数 - 递推公式：
dp[i][j] = dp[i-1][j] + dp[i][j-1] - 初始化：第一行
dp[0][j] = 1，第一列dp[i][0] = 1 - 遍历顺序：从左到右，从上到下（依赖上方和左方）
- 举例验证：m=3, n=3 → 第一行 [1,1,1], 第一列 [1,1,1]; dp[1][1]=1+1=2, dp[1][2]=1+2=3, dp[2][1]=1+2=3, dp[2][2]=3+3=6 ✓
def uniquePaths(m, n):
# 创建全 1 的 m x n 网格，第一行和第一列已正确初始化
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]思路二：空间优化 DP（一维数组）
由于 dp[i][j] 只依赖本行的前一列 dp[i][j-1] 和上一行的同列 dp[i-1][j]，滚动数组只用一维。
def uniquePaths(m, n):
dp = [1] * n # 第一行全为 1
for _ in range(1, m): # 遍历剩余行
for j in range(1, n): # 每行从第 2 列开始
dp[j] += dp[j - 1] # dp[j] = dp[j](上一行) + dp[j-1](本行左)
return dp[-1] # 右下角思路三：组合数学
总步数 = (m-1)+(n-1) = m+n-2，选择其中 n-1 步向右走（或 m-1 步向下走）。
import math
def uniquePaths(m, n):
# C(m+n-2, n-1) 或 C(m+n-2, m-1)
return math.comb(m + n - 2, n - 1)易错点
- 索引范围：dp 数组是 m x n，但递推时从 i=1, j=1 开始，避免访问
dp[-1]。 - 初始化：第一行
dp[0][j]和第一列dp[i][0]都是 1（不是 0！），因为只有一条路径。 - m, n 输入顺序：m 是行数，n 是列数。创建数组时
dp = [[1]*n for _ in range(m)]。 - 组合数溢出：Python 的 math.comb 可以处理大数，但 C 语言等需注意溢出。
框架提炼
二维计数 DP 模板（依赖上方和左方）：
def grid_path_count(m, n):
dp = [[1] * n for _ in range(m)] # 初始化为 1（第一行第一列已正确）
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 转移方程
return dp[m - 1][n - 1]空间优化版：
def grid_path_count_optimized(m, n):
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[-1]关联题目
- 64-最小路径和 — 相同网格结构，求和变为取最小值
- 63-不同路径 II — 带障碍物版本，遇到障碍 dp 值设为 0
- 118-杨辉三角 — 递推关系
dp[i][j] = dp[i-1][j] + dp[i][j-1]与杨辉三角本质相同