题目描述
思路解析
一句话答案：LeetCode 62 不同路径的标准解法是二维动态规划：机器人只能向右或向下走，到达任意格子只可能来自正上方或正左方，故 dp[i][j] = dp[i-1][j] + dp[i][j-1]，其中 dp[i][j] 是走到 (i,j) 的路径数，第一行第一列全为 1。时间 O(m×n)，空间可压缩到 O(n)。
不同路径这道题在问什么
一个 m 行 n 列的网格，机器人从左上角 (0,0) 出发，每一步只能向右或向下移动一格，问走到右下角 (m-1,n-1) 共有多少条不同的路径。要求的是路径条数而不是最短路——每条合法路径长度其实都一样（恰好右移 n-1 次、下移 m-1 次），区别只在这些移动的先后顺序。m=4、n=5 时答案是 35。
为什么想到用动态规划数路径
直接搜索是可行的起点：从起点出发递归枚举每一步向右还是向下，走到终点计一条。但路径条数随网格尺寸指数级增长，纯递归会把同一个格子的子问题重复算无数遍——走到 (2,2) 的方式有很多种，可从 (2,2) 到终点的路径数只需要算一次。
关键观察是反过来看：由于只能向右或向下，任何一条到达 (i,j) 的路径，最后一步只有两种可能——从正上方 (i-1,j) 下来，或从正左方 (i,j-1) 过来，不存在第三个入口。这两类路径最后一步不同，必然互不重复；而所有路径又必属其一，不会遗漏。于是「到 (i,j) 的路径数 = 到上方的路径数 + 到左方的路径数」，加法原理保证不重不漏，问题被拆成规模更小的同类问题。
dp 数组怎么定义，第一行第一列为什么全是 1
定义 dp[i][j] 为从起点 (0,0) 走到 (i,j) 的不同路径条数，答案就是 dp[m-1][n-1]。边界要先铺好：第一行的格子上方没有格子，只能从左边一路向右走过来，路径只有一条；同理第一列只能一路向下。所以第一行、第一列全部初始化为 1，起点 dp[0][0]=1 也读作「原地不动算一种走法」。
这个初始化是整张表的地基。忘了铺 1、留成 0，后面每一格都是在 0 上做加法，整张表全错——这是本题最常见的错误。
转移方程为什么成立，从哪一格开始填
内部格子套 dp[i][j] = dp[i-1][j] + dp[i][j-1]。它成立的依据就是上面的两入口观察：两个来源的路径集合互斥且完备，条数直接相加。填表顺序按行从上到下、每行从左到右，保证算任何一格时它的上方和左方已经算好。
主循环要从 (1,1) 开始而不是 (0,0)：边界已经填好了，从 (1,1) 起每一格才同时有「上」和「左」可加。以样例收尾验证一下，右下角累加出 dp[3][4]=35，与答案一致。
复杂度多少，空间怎么压到一行
时间复杂度 O(m×n)：每个格子只被计算一次，每次是一次加法。空间 O(m×n) 存整张表；由于每格只依赖上一行同列和本行左邻，可以用一维数组滚动更新 dp[j] += dp[j-1]，空间降到 O(n)。
一个常见的延伸问法：如果网格里有障碍物（LeetCode 63 不同路径 II），框架不变，把障碍格的 dp 直接置 0 表示走不到，其余格照样上加左；若起点本身是障碍，答案直接为 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句「上面来 + 左边来」，下面每一格都在套它。
起点 (0,0)：原地不动也算一种走法，dp[0][0] = 1。
第一行 (0,1)：上面没有格子，只能从左边一路向右走过来，dp[0][1] = 1。
第一行 (0,2)：上面没有格子，只能从左边一路向右走过来，dp[0][2] = 1。
第一行 (0,3)：上面没有格子，只能从左边一路向右走过来，dp[0][3] = 1。
第一行 (0,4)：上面没有格子，只能从左边一路向右走过来，dp[0][4] = 1。
第一列 (1,0)：左边没有格子，只能从上面一路向下走过来，dp[1][0] = 1。
算 (1,1)：正上方 dp[0][1]=1（蓝），正左方 dp[1][0]=1（蓝），两条路汇到这里。
相加：1 + 1 = 2，填进 (1,1)。从上面来的 1 条、从左边来的 1 条，合起来就这么多。
算 (1,2)：正上方 dp[0][2]=1（蓝），正左方 dp[1][1]=2（蓝），两条路汇到这里。
相加：1 + 2 = 3，填进 (1,2)。从上面来的 1 条、从左边来的 2 条，合起来就这么多。
算 (1,3)：正上方 dp[0][3]=1（蓝），正左方 dp[1][2]=3（蓝），两条路汇到这里。
相加：1 + 3 = 4，填进 (1,3)。从上面来的 1 条、从左边来的 3 条，合起来就这么多。
算 (1,4)：正上方 dp[0][4]=1（蓝），正左方 dp[1][3]=4（蓝），两条路汇到这里。
相加：1 + 4 = 5，填进 (1,4)。从上面来的 1 条、从左边来的 4 条，合起来就这么多。
第一列 (2,0)：左边没有格子，只能从上面一路向下走过来，dp[2][0] = 1。
算 (2,1)：正上方 dp[1][1]=2（蓝），正左方 dp[2][0]=1（蓝），两条路汇到这里。
相加：2 + 1 = 3，填进 (2,1)。从上面来的 2 条、从左边来的 1 条，合起来就这么多。
算 (2,2)：正上方 dp[1][2]=3（蓝），正左方 dp[2][1]=3（蓝），两条路汇到这里。
相加：3 + 3 = 6，填进 (2,2)。从上面来的 3 条、从左边来的 3 条，合起来就这么多。
算 (2,3)：正上方 dp[1][3]=4（蓝），正左方 dp[2][2]=6（蓝），两条路汇到这里。
相加：4 + 6 = 10，填进 (2,3)。从上面来的 4 条、从左边来的 6 条，合起来就这么多。
算 (2,4)：正上方 dp[1][4]=5（蓝），正左方 dp[2][3]=10（蓝），两条路汇到这里。
相加：5 + 10 = 15，填进 (2,4)。从上面来的 5 条、从左边来的 10 条，合起来就这么多。
第一列 (3,0)：左边没有格子，只能从上面一路向下走过来，dp[3][0] = 1。
算 (3,1)：正上方 dp[2][1]=3（蓝），正左方 dp[3][0]=1（蓝），两条路汇到这里。
相加：3 + 1 = 4，填进 (3,1)。从上面来的 3 条、从左边来的 1 条，合起来就这么多。
算 (3,2)：正上方 dp[2][2]=6（蓝），正左方 dp[3][1]=4（蓝），两条路汇到这里。
相加：6 + 4 = 10，填进 (3,2)。从上面来的 6 条、从左边来的 4 条，合起来就这么多。
算 (3,3)：正上方 dp[2][3]=10（蓝），正左方 dp[3][2]=10（蓝），两条路汇到这里。
相加：10 + 10 = 20，填进 (3,3)。从上面来的 10 条、从左边来的 10 条，合起来就这么多。
算 (3,4)：正上方 dp[2][4]=15（蓝），正左方 dp[3][3]=20（蓝），两条路汇到这里。
相加：15 + 20 = 35，填进 (3,4)。从上面来的 15 条、从左边来的 20 条，合起来就这么多。
表填满了。右下角 dp[3][4] = 35，就是机器人从左上走到右下的不同路径总数。
极端输入正好被「第一行/列全 1」覆盖。
两个高频追问。
参考代码
def uniquePaths(m, 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]复杂度
- 时间：O(m×n)，每格只算一次
- 空间：O(m×n)，存了整张表（可压成一行 O(n)）
易错点
面试追问把动画讲成自己的话
追问如果网格里有障碍物（LC63）怎么改？
追问能优化到 O(n) 空间吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长公共子序列
LeetCode 1143 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题