LeetCode-062不同路径，走法数怎么算？
摘要：本题在线练习：LeetCode 62. 不同路径 - 在线练习（免费 · 无需登录 · AI 辅助）(https:onefly.topzero2Leetcodeplayground
本题在线练习：LeetCode 62. 不同路径 - 在线练习（免费 · 无需登录 · AI 辅助）(https://onefly.top/zero2Leetcode/playground.html?id=62)
配套刷题网站 Zero2Leetcode —— 内置本地 OJ + AI 教练，零门槛开始刷 Hot 100。
题目概述
在一个 m x n 的网格中，机器人从左上角出发，每一步只能 向右 或 向下，问到达右下角一共有多少条不同路径。
这题看起来是“走迷宫”，但本质是一个非常典型的动态规划入门题：每个格子的路径数只取决于它的“上方”和“左方”。
核心思路：到达 (i, j) 的路径数从哪里来
设 dp[i][j] 表示到达格子 (i, j) 的不同路径数（i 从 0 到 m-1，j 从 0 到 n-1）。
到达 (i, j) 只有两种最后一步：
从上方 (i-1, j) 向下走一步
从左方 (i, j-1) 向右走一步
所以转移方程很自然：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界条件：
第一行只能一直向右走：dp[0][j] = 1
第一列只能一直向下走：dp[i][0] = 1
先从最自然的版本讲起：二维 DP
二维 DP 直观，便于理解“上方 + 左方”的含义。
代码实现（二维 dp）
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 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]
逐行拆解：为什么这样填表
dp[i][0] = 1：在第一列，想从 (0,0) 到 (i,0) 只能一直向下，没有分岔。
dp[0][j] = 1：在第一行同理，只能一直向右。
从 (1,1) 开始填表：每个格子都能从上或左到达，路径数就是两者之和。
手动模拟：m=3, n=7 的“填表过程”
初始化第一行/列为 1：
1 1 1 1 1 1 1
1 0 0 0 0 0 0
1 0 0 0 0 0 0
从 (1,1) 开始：
dp[1][1] = 1 + 1 = 2
dp[1][2] = 1 + 2 = 3
...
最终会得到右下角的答案。
进阶：空间优化到一维 DP（更推荐的写法）
观察转移：dp[i][j] 只依赖“上一行同列”和“当前行前一列”。如果用一维数组 dp[j] 表示当前行的结果：
dp[j] 在更新前是上一行的 dp[i-1][j]
dp[j-1] 已经是当前行的 dp[i][j-1]
所以：
dp[j] = dp[j] + dp[j-1]
代码实现（一维 dp）
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n # 第一行全是 1
for _ in range(1, m):
for j in range(1, n):
dp[j] = dp[j] + dp[j - 1]
return dp[-1]
复杂度分析
二维 DP：时间 O(mn)，空间 O(mn)
一维 DP：时间 O(mn)，空间 O(n)
对比与总结
这题最值得带走的不是“背下代码”，而是这句话：
“走到一个格子的路径数 = 走到它上面格子的路径数 + 走到它左边格子的路径数。”
掌握这个“从最后一步倒推”的思考方式，后面大量网格 DP（最小路径和、不同路径 II 等）都会非常顺。
结尾
不同路径是网格 DP 的标准起点。把 dp[i][j] 的定义说清楚、把边界条件想明白，再写代码就只是把逻辑翻译成循环而已。