不同路径 II 图解题解
这道题到底在问什么
- 输入
- 4×6 网格，障碍在 (0,3)(1,1)(2,3)
- 输出
- 7
最优解：为什么这么做
一句话答案：LeetCode 63 不同路径 II 在带障碍网格里数路径，二维 DP：dp[i][j]=dp[i-1][j]+dp[i][j-1] 记走到该格的路数，障碍格置 0 阻断下游，时间 O(m×n)、空间可压 O(n)。
不同路径 II 到底在数什么
给一个 m×n 网格，0 是空地、1 是障碍。机器人从左上角 (0,0) 出发，每步只能向右或向下，问走到右下角、不踩任何障碍的不同路径有多少条。本题网格是 4 行 6 列，障碍摆在 (0,3)、(1,1)、(2,3)，答案是 7。
为什么不能把每条路都走一遍数
最直接是把每条路都走出来数一遍：从左上到右下走 m+n-2 步、每步二选一，路径数随网格指数级膨胀，稍大就数不完。浪费在于：走到中间某格的路数，会在很多条完整路径里被反复重算。既然「走到某格有几条路」这个子问题能独立回答，就算一次存下来，指数枚举压成一格一格填的递推——用填好的格子推当前格，就是动态规划（DP，把子问题的答案记下来别重算）。
dp[i][j] 记什么，障碍格为什么直接记 0
定义 dp[i][j] 为「从起点走到格子 (i,j) 的不同路径数」。走到 (i,j) 的最后一步，要么从正上方 (i-1,j) 下来、要么从正左方 (i,j-1) 过来，两批路互不重叠，所以 dp[i][j]=dp[i-1][j]+dp[i][j-1]。起点 dp[0][0]=1，原地不动也算一种走法。
和无障碍版唯一的差别就在障碍格：机器人踏不进去，走到它的路数只能是 0，遇到障碍直接 dp[i][j]=0，不做相加。
障碍格的 0 怎么自然把下游路径掐断
障碍格记 0，会顺着转移式（由已算好的格子推出当前格子的那条公式）自动把下游的路堵死，不用额外判断。障碍被置 0 后，它下方和右方的格子相加时，把这个 0 当成一条来路，相当于「从障碍过来有 0 条路」。比如障碍右邻那格，正常是「上方 + 左方」，可左方是障碍的 0，只剩上方一条贡献。障碍一格 0，只掐掉穿过它的路，不会误伤其余。
拿题面 4×6 网格把整张表填一遍
按题面 4×6 网格逐格填。第 0 行：dp[0][0]=1，(0,1)(0,2) 只有左边一条来路照搬得 1、1；(0,3) 障碍记 0；(0,4)(0,5) 唯一来路是左边那个 0，也跟着变 0。
第 1 行：(1,0) 从上方来是 1；(1,1) 障碍记 0；(1,2)=1+0=1，(1,3)=0+1=1，(1,4)=0+1=1，(1,5)=0+1=1。第 2 行：(2,0)=1，(2,1)=0+1=1，(2,2)=1+1=2，(2,3) 障碍记 0，(2,4)=1+0=1，(2,5)=1+1=2。
第 3 行：(3,0)=1，(3,1)=1+1=2，(3,2)=2+2=4，(3,3)=0+4=4，(3,4)=1+4=5，(3,5)=2+5=7。右下角 dp[3][5]=7，就是绕开 3 个障碍的路径总数。
复杂度多少，起点和首行遇障碍两个边界
每格只算一次加法、共 m×n 格，时间 O(m×n)；dp 表可压成一行滚动更新（滚动数组：只留一行滚动覆盖），空间从 O(m×n) 降到 O(n)。
两个边界最容易踩坑。一是起点就是障碍：出发点都踏不进去，直接返回 0，别再往下填。二是首行或首列遇障碍：这一行/列只有一条直线来路，障碍之后的格子来路被掐断，必须跟着全变 0，无脑填 1 就写错了。
▶ 动画逐步走查（共 39 步）——想跟着动画一帧帧对照就展开
- 3和无障碍版唯一的差别：遇到障碍格，这一格直接填 0，不再相加。记住这一点，下面每格都在套它。
- 4起点 (0,0)：原地不动也算一种走法，dp[0][0] = 1。
- 5(0,1) 在边上，只有一条来路（左方 dp[0][0]=1），照搬过来 dp[0][1] = 1。
- 6(0,2) 在边上，只有一条来路（左方 dp[0][1]=1），照搬过来 dp[0][2] = 1。
- 7(0,3) 是障碍格（█），机器人根本踏不进来，路径数记 0——它不给下游贡献任何走法。
- 8(0,4) 在边上，唯一来路（左方 dp[0][3]=0）已经是 0——前面被障碍掐断了，所以这里也走不到，dp=0。
- 9(0,5) 在边上，唯一来路（左方 dp[0][4]=0）已经是 0——前面被障碍掐断了，所以这里也走不到，dp=0。
- 10(1,0) 在边上，只有一条来路（上方 dp[0][0]=1），照搬过来 dp[1][0] = 1。
- 11(1,1) 是障碍格（█），机器人根本踏不进来，路径数记 0——它不给下游贡献任何走法。
- 12算 (1,2)：正上方 dp[0][2]=1（蓝），正左方 dp[1][1]=0（蓝），两条来路汇到这里。
- 13相加：1 + 0 = 1，填进 (1,2)。有一条来路是 0（被障碍堵了），只剩另一条贡献。
- 14算 (1,3)：正上方 dp[0][3]=0（蓝），正左方 dp[1][2]=1（蓝），两条来路汇到这里。
- 15相加：0 + 1 = 1，填进 (1,3)。有一条来路是 0（被障碍堵了），只剩另一条贡献。
- 16算 (1,4)：正上方 dp[0][4]=0（蓝），正左方 dp[1][3]=1（蓝），两条来路汇到这里。
- 17相加：0 + 1 = 1，填进 (1,4)。有一条来路是 0（被障碍堵了），只剩另一条贡献。
- 18算 (1,5)：正上方 dp[0][5]=0（蓝），正左方 dp[1][4]=1（蓝），两条来路汇到这里。
- 19相加：0 + 1 = 1，填进 (1,5)。有一条来路是 0（被障碍堵了），只剩另一条贡献。
- 20(2,0) 在边上，只有一条来路（上方 dp[1][0]=1），照搬过来 dp[2][0] = 1。
- 21算 (2,1)：正上方 dp[1][1]=0（蓝），正左方 dp[2][0]=1（蓝），两条来路汇到这里。
- 22相加：0 + 1 = 1，填进 (2,1)。有一条来路是 0（被障碍堵了），只剩另一条贡献。
- 23算 (2,2)：正上方 dp[1][2]=1（蓝），正左方 dp[2][1]=1（蓝），两条来路汇到这里。
- 24相加：1 + 1 = 2，填进 (2,2)。从上面来的、从左边来的，合起来就这么多。
- 25(2,3) 是障碍格（█），机器人根本踏不进来，路径数记 0——它不给下游贡献任何走法。
- 26算 (2,4)：正上方 dp[1][4]=1（蓝），正左方 dp[2][3]=0（蓝），两条来路汇到这里。
- 27相加：1 + 0 = 1，填进 (2,4)。有一条来路是 0（被障碍堵了），只剩另一条贡献。
- 28算 (2,5)：正上方 dp[1][5]=1（蓝），正左方 dp[2][4]=1（蓝），两条来路汇到这里。
- 29相加：1 + 1 = 2，填进 (2,5)。从上面来的、从左边来的，合起来就这么多。
- 30(3,0) 在边上，只有一条来路（上方 dp[2][0]=1），照搬过来 dp[3][0] = 1。
- 31算 (3,1)：正上方 dp[2][1]=1（蓝），正左方 dp[3][0]=1（蓝），两条来路汇到这里。
- 32相加：1 + 1 = 2，填进 (3,1)。从上面来的、从左边来的，合起来就这么多。
- 33算 (3,2)：正上方 dp[2][2]=2（蓝），正左方 dp[3][1]=2（蓝），两条来路汇到这里。
- 34相加：2 + 2 = 4，填进 (3,2)。从上面来的、从左边来的，合起来就这么多。
- 35算 (3,3)：正上方 dp[2][3]=0（蓝），正左方 dp[3][2]=4（蓝），两条来路汇到这里。
- 36相加：0 + 4 = 4，填进 (3,3)。有一条来路是 0（被障碍堵了），只剩另一条贡献。
- 37算 (3,4)：正上方 dp[2][4]=1（蓝），正左方 dp[3][3]=4（蓝），两条来路汇到这里。
- 38相加：1 + 4 = 5，填进 (3,4)。从上面来的、从左边来的，合起来就这么多。
- 39算 (3,5)：正上方 dp[2][5]=2（蓝），正左方 dp[3][4]=5（蓝），两条来路汇到这里。
- 40相加：2 + 5 = 7，填进 (3,5)。从上面来的、从左边来的，合起来就这么多。
- 41表填满了。右下角 dp[3][5] = 7，就是绕开 3 个障碍、从左上走到右下的不同路径总数。
⚠️ 容易写错的地方
✗ 错：障碍格忘了置 0 照样相加
✓ 对：障碍格 dp 必须 = 0
它走不到，给下游贡献 0 条路
✗ 错：首行/首列无脑全填 1
✓ 对：遇障碍后续要变 0
来路被堵，后面格子也到不了
✗ 错：起点是障碍没特判
✓ 对：起点障碍直接答案 0
出发点都站不了，无路可走
完整代码（Python / C++ / Java）
Python
def uniquePathsWithObstacles(g):
m, n = len(g), len(g[0])
if g[0][0] == 1: return 0
dp = [[0]*n for _ in range(m)]
dp[0][0] = 1
for i in range(m):
for j in range(n):
if g[i][j] == 1:
dp[i][j] = 0
elif i or j:
up = dp[i-1][j] if i else 0
lf = dp[i][j-1] if j else 0
dp[i][j] = up + lf
return dp[m-1][n-1]C++
int uniquePathsWithObstacles(vector<vector<int>>& g){
int m = g.size(), n = g[0].size();
if(g[0][0] == 1) return 0;
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(g[i][j] == 1){ dp[i][j] = 0; continue; }
if(i==0 && j==0) continue;
int up = i ? dp[i-1][j] : 0;
int lf = j ? dp[i][j-1] : 0;
dp[i][j] = up + lf;
}
return dp[m-1][n-1];Java
int uniquePathsWithObstacles(int[][] g){
int m = g.length, n = g[0].length;
if (g[0][0] == 1) return 0;
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (g[i][j] == 1) { dp[i][j] = 0; continue; }
if (i == 0 && j == 0) continue;
int up = i > 0 ? dp[i - 1][j] : 0;
int lf = j > 0 ? dp[i][j - 1] : 0;
dp[i][j] = up + lf;
}
return dp[m - 1][n - 1];复杂度
时间
O(m×n)
每格只算一次
空间
O(m×n)
存整张表（可压成一行 O(n)）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 不同路径 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
障碍格为什么是置 0，而不是跳过不填？+
置 0 和「跳过」效果完全不同。障碍格下游的格子在相加时要读它的值，如果不填、留着初始值或残值，下游就会把错误的路数加进去。填 0 明确表示「从障碍这条来路过来有 0 条路」，下游相加时这条自然不贡献，路径被精准掐断，其余来路照常累加。
起点或终点是障碍会怎样？+
起点是障碍要单独特判，直接返回 0——出发点都踏不进去，一条路都没有。终点是障碍则不用特判：它会被正常置 0，最后返回 dp[m-1][n-1] 就是 0，自然表示走不到。
能优化到 O(n) 空间吗？+
能。转移式 dp[i][j]=dp[i-1][j]+dp[i][j-1] 算当前行只用到上一行同列和当前行左边，用一维 dp[j] 逐行滚动覆盖即可：障碍处置 dp[j]=0，否则 dp[j]+=dp[j-1]。空间从 O(m×n) 降到 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 不同路径 II 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。