§1

题目描述

机器人在 m×n 网格左上角，每次只能向右或向下，到右下角共几条路径？

网格 = 3 × 3

输出 = 6

另例 = 3 × 7 → 28

§2

思路解析动画文字版

一条条枚举走法，3×3 还能硬数出 6 条；网格一大，走法数就是组合数 C(m+n−2, n−1)，爆炸式增长，根本数不过来。痛点在于：同一个格子被反复经过、重复计算——左上角那块路径，几乎每条大路都要重新走一遍。

与其重复数每条路，不如把每个格子的走法数记进一张表。一个格子只能从上面或左边过来，所以 dp[i][j] = 上 + 左 = dp[i-1][j] + dp[i][j-1]。为什么能这么拆？因为「到 (i,j) 的路」按最后一步是「从上来」还是「从左来」不重不漏地分成两类，而上、左两格早算好了——直接查表相加，绝不重算。

建表：建一张 3×3 的表，每格存「到这里的路径数」。起点 (0,0) 只有 1 种走法（站着不动），先把它当锚点。终点是右下角 dp[2][2]，咱一格一格填过去。

第一行 = 1：最上面一行没有「上面」可来，只能从起点一路向右，所以到行0每一格都只有 1 种走法，全填 1。

第一列 = 1：同理，最左边一列没有「左边」可来，只能一路向下，每格也是 1。第一行、第一列是边界——它们撑不起转移方程，必须单独定。

关键：上 + 左：第一个真正用到转移方程的格子。dp[1][1] 看两个依赖格：正上方 dp[0][1]=1、正左方 dp[1][0]=1，相加 = 2。这就是「上 + 左」。

填 dp[1][2]：同一招：上面 dp[0][2]=1，左边 dp[1][1]=2（刚算出来的），相加 = 3。注意左边那格的答案是上一步现成存好的，直接拿来用。

填 dp[2][1]：换到第三行。dp[2][1] 的上面是 dp[1][1]=2、左边是 dp[2][0]=1，相加 = 3。填表顺序从上到下、从左到右，保证依赖格永远先算好。

填到右下角：终点格。上面 dp[1][2]=3，左边 dp[2][1]=3，相加 = 6。两条「来路」各 3 条，合起来正好 6。

答案：表填满了，右下角 dp[2][2] = 6 就是答案，和一开始手数的 6 条路完全对上。

DP 说白了就是「走过的路记下来，绝不重复算」。「每格只看上和左」只是这个思想落在网格里的样子——最小路径和、三角形最小和都是同一招。

雷区实演：漏填边界：把口头警告演成看得见的后果：第一行/列忘了填 1、全留 0，到 dp[1][1] 时上 0＋左 0＝0，往后每格都是 0＋0，整张表全被传染成 0，右下角答案也成了 0。对比前面填对的表——差别只在那圈边界有没有填 1。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。想验收，可以让小欧 AI 私教随机抽 LC64 让你口述转移方程，或直接去通关训练里连刷这一类。

边界三连：边界三连：极端输入先过一遍。1×1、单行、单列都只有 1 条路，正好被「第一行/列全填 1」覆盖，不用写特判。

几个高频追问，记住答法。

§3

参考代码

class Solution:    def uniquePaths(self, m, n):        dp = [[0] * n for _ in range(m)]        for j in range(n): dp[0][j] = 1   # 第一行        for i in range(m): dp[i][0] = 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]

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(m×n)，每格只算一次，共 m×n 格
空间复杂度：O(m×n)，存了整张二维表

§5

可套用的代码模板

把参考代码挖空成可背骨架：先定第一行/列边界，再双层循环把「上和左」合并。本题「合并」=相加、「当前格」=0，就是不同路径；最小路径和把「合并」换成 min、「当前格」换成格子代价；不同路径II 把障碍格的边界值/dp 直接置 0——同一副骨架，换两个空就是一道新题。

# 凡是「网格里从左上走到右下」的题都能套dp = [[0]*n for _ in range(m)]for i in range(m): dp[i][0] = 边界值   # 第一列for j in range(n): dp[0][j] = 边界值   # 第一行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]

§6

易错点

✗ 错误写法：第一行/列不初始化为 1

✓ 正确写法：先把第一行、第一列每格填 1

边界格没有「上」或「左」可加；不填成 1，dp[1][1] 就会从一堆 0 算出 0，整张表全错

✗ 错误写法：内层 j 从 0 开始

✓ 正确写法：i、j 都从 1 开始（边界已填）

从 0 开始会覆盖已填好的第一列；在 Python 里 dp[i][j-1] 还会取到 dp[i][-1]=末列，数值错得没报错

面试追问把动画讲成自己的话

追问为什么是相加不是相乘？

到 (i,j) 的每条路径最后一步要么从上、要么从左，两类不重叠也不遗漏，所以是路径数相加；相乘是「分步都要做」的乘法原理，这里是「二选一」，用加法。

追问能优化空间吗？

能。每格只依赖上一行和同行左边，可以把二维表压成一行滚动数组：dp[j] += dp[j-1]，空间从 O(m×n) 降到 O(n)。

追问有数学公式吗？

有，组合数 C(m+n-2, m-1)：总共走 m+n-2 步、从中选 m-1 步向下，O(1) 出答案（但要会推 DP，面试看的是思路）。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 二维动态规划 2/15

最长公共子序列

LeetCode 1143 · 中等 · 沿着二维动态规划继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

class Solution: def uniquePaths(self, m, n): dp = [[0] * n for _ in range(m)] for j in range(n): dp[0][j] = 1 # 第一行 for i in range(m): dp[i][0] = 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 = [[0]*n for _ in range(m)]for i in range(m): dp[i][0] = 边界值 # 第一列for j in range(n): dp[0][j] = 边界值 # 第一行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]