LeetCode 62中等二维 DP
不同路径 图解题解
这道题到底在问什么
机器人在 m×n 网格左上角，每次只能向右或向下，到右下角共几条路径？
- 网格
- 3 × 3
- 输出
- 6
- 另例
- 3 × 7 → 28
先想最直接的笨办法
一条条枚举走法，3×3 还能硬数出 6 条；网格一大，走法数就是组合数 C(m+n−2, n−1)，爆炸式增长，根本数不过来。痛点在于：同一个格子被反复经过、重复计算——左上角那块路径，几乎每条大路都要重新走一遍。（动画第 3 步）
最优解：一步一步想明白
- 3一条条枚举走法，3×3 还能硬数出 6 条；网格一大，走法数就是组合数 C(m+n−2, n−1)，爆炸式增长，根本数不过来。痛点在于：同一个格子被反复经过、重复计算——左上角那块路径，几乎每条大路都要重新走一遍。
- 4与其重复数每条路，不如把每个格子的走法数记进一张表。一个格子只能从上面或左边过来，所以 dp[i][j] = 上 + 左 = dp[i-1][j] + dp[i][j-1]。为什么能这么拆？因为「到 (i,j) 的路」按最后一步是「从上来」还是「从左来」不重不漏地分成两类，而上、左两格早算好了——直接查表相加，绝不重算。
- 53×3 全空建一张 3×3 的表，每格存「到这里的路径数」。起点 (0,0) 只有 1 种走法（站着不动），先把它当锚点。终点是右下角 dp[2][2]，咱一格一格填过去。
- 6最上行只能一直向右最上面一行没有「上面」可来，只能从起点一路向右，所以到行0每一格都只有 1 种走法，全填 1。
- 7最左列只能一直向下同理，最左边一列没有「左边」可来，只能一路向下，每格也是 1。第一行、第一列是边界——它们撑不起转移方程，必须单独定。
- 8dp[1][1] = 1+1 = 2第一个真正用到转移方程的格子。dp[1][1] 看两个依赖格：正上方 dp[0][1]=1、正左方 dp[1][0]=1，相加 = 2。这就是「上 + 左」。
- 9= 上1 + 左2 = 3同一招：上面 dp[0][2]=1，左边 dp[1][1]=2（刚算出来的），相加 = 3。注意左边那格的答案是上一步现成存好的，直接拿来用。
- 10= 上2 + 左1 = 3换到第三行。dp[2][1] 的上面是 dp[1][1]=2、左边是 dp[2][0]=1，相加 = 3。填表顺序从上到下、从左到右，保证依赖格永远先算好。
- 11dp[2][2] = 上3 + 左3 = 6终点格。上面 dp[1][2]=3，左边 dp[2][1]=3，相加 = 6。两条「来路」各 3 条，合起来正好 6。
- 12dp[2][2] = 6表填满了，右下角 dp[2][2] = 6 就是答案，和一开始手数的 6 条路完全对上。
- 15DP 说白了就是「走过的路记下来，绝不重复算」。「每格只看上和左」只是这个思想落在网格里的样子——最小路径和、三角形最小和都是同一招。
- 18边界全留 0 → 整表归零把口头警告演成看得见的后果：第一行/列忘了填 1、全留 0，到 dp[1][1] 时上 0＋左 0＝0，往后每格都是 0＋0，整张表全被传染成 0，右下角答案也成了 0。对比前面填对的表——差别只在那圈边界有没有填 1。
- 21把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。想验收，可以让小欧 AI 私教随机抽 LC64 让你口述转移方程，或直接去通关训练里连刷这一类。
⚠️ 容易写错的地方
✗ 错：第一行/列不初始化为 1
✓ 对：先把第一行、第一列每格填 1
边界格没有「上」或「左」可加；不填成 1，dp[1][1] 就会从一堆 0 算出 0，整张表全错
✗ 错：内层 j 从 0 开始
✓ 对：i、j 都从 1 开始（边界已填）
从 0 开始会覆盖已填好的第一列；在 Python 里 dp[i][j-1] 还会取到 dp[i][-1]=末列，数值错得没报错
完整代码（Python / C++ / Java）
Python
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]C++
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int j = 0; j < n; j++) dp[0][j] = 1; // 第一行
for (int i = 0; i < m; i++) dp[i][0] = 1; // 第一列
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 上 + 左
return dp[m-1][n-1];
}
};Java
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int j = 0; j < n; j++) dp[0][j] = 1; // 第一行
for (int i = 0; i < m; i++) dp[i][0] = 1; // 第一列
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 上 + 左
return dp[m-1][n-1];
}
}套路模板 · 网格DP「上 + 左」（背下来）
# 凡是「网格里从左上走到右下」的题都能套
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]// 网格DP骨架：定边界 → 双层循环合并上和左
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 边界值; // 第一列
for (int j = 0; j < n; j++) dp[0][j] = 边界值; // 第一行
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = 合并(dp[i-1][j], dp[i][j-1]) + 当前格;
return dp[m-1][n-1];// 网格DP骨架：定边界 → 双层循环合并上和左
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 边界值; // 第一列
for (int j = 0; j < n; j++) dp[0][j] = 边界值; // 第一行
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = 合并(dp[i-1][j], dp[i][j-1]) + 当前格;
return dp[m-1][n-1];复杂度
时间复杂度
O(m×n)
每格只算一次，共 m×n 格
空间复杂度
O(m×n)
存了整张二维表
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 不同路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么是相加不是相乘？+
到 (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，面试看的是思路）。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。