华为 OD 训练营 · 题解精讲
LC62. 不同路径
配套讲解：视频讲解 ↗
LC62. 不同路径 视频地址：https://uha.xet.tech/s/4iPP5q
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ I5Aab7QCjoatk4xqriOcIEzCnHf.png
题目解析
解题思路
本题是典型的动态规划问题。机器人每次只能向下或向右移动，因此到达任意格子 (i, j) 的路径只能来自上方 (i-1, j) 或左方 (i, j-1)。使用二维数组 dp 记录到达每个格子的路径数，状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
关键步骤
1. 初始化：dp[0][0] = 1，表示起点只有一条路径（即原地不动）。 2. 边界处理：第一列（i 从 1 到 m-1）只能从上方向下走，路径数均为 1；第一行（j 从 1 到 n-1）只能从左方向右走，路径数也均为 1。 3. 填充 DP 表：从 (1,1) 到 (m-1, n-1) 逐行逐列计算，每个格子的值等于上方格子与左方格子之和。
示意图（以 3×3 为例，数字表示路径数）：
[1] [1] [1]
[1] [2] [3]
[1] [3] [6]复杂度分析
- 时间复杂度：O(m×n)，需要遍历整个网格一次。
- 空间复杂度：O(m×n)，使用了一个 m 行 n 列的二维数组存储中间结果。
参考代码
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
# dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
# dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
dp = [[0] * n for _ in range(m)]
# 初始化 dp[0][0]，
# dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
# 仅此一条，别无分路
dp[0][0] = 1
# i 从 1 遍历到 m - 1
# 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向下移动一步
# 所以，只能一直向下走，只有这一条路径
for i in range( 1 , m ):
# 仅此一条，别无分路
dp[i][0] = 1
# j 从 1 遍历到 n - 1
# 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向右移动一步
# 所以，只能一直向右走，只有这一条路径
for j in range( 1 , n ):
# 仅此一条，别无分路
dp[0][j] = 1
# 接下来从第 1 行到第 m - 1 行
# 从第 1 列到 n - 1 列
# 填充二维数组 dp 里面的值
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
for i in range( 1 , m ):
for j in range( 1 , n ):
# 由于每次只能向下或者向右移动一步
# 位置 (i,j) 的不同路径的数量是由
# 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
# 2、左边位置 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 ]