出界的路径数 图解题解
这道题到底在问什么
- 输入
- m=2,n=2,maxMove=2,start=(0,0)
- 输出
- 6(两步内 6 条出界路径)
- 输入
- m=1,n=1,maxMove=1,start=(0,0)
- 输出
- 4(一步,四个方向都出界)
最优解：一步一步想明白
- 3记住「每步把 dp 往四周扩散:界内进 ndp、越界进 ans」,下面逐步套它。
- 4初始 dp 网格:只有起点 (0,0) 是 1(高亮),其余为 0。ans 从 0 开始累计出界路径。
- 5开始第 1/2 步。新建空的 ndp,准备接收扩散结果;ans 当前 = 0。
- 6看 dp[0][0]=1(紫):它会把这 1 条路径分别推向上下左右四个邻居。
- 7从 (0,0) 往下到界内的 (1,0)(蓝),把 1 条路径累加进 ndp,ndp[1][0] 现为 1。
- 8从 (0,0) 往上走出网格了,这 1 条路径正好在第 1 步出界,计入 ans,现 ans = 1。
- 9从 (0,0) 往右到界内的 (0,1)(蓝),把 1 条路径累加进 ndp,ndp[0][1] 现为 1。
- 10从 (0,0) 往左走出网格了,这 1 条路径正好在第 1 步出界,计入 ans,现 ans = 2。
- 11第 1 步扩散完毕,用 ndp 替换 dp(现在网格里的数是「走 1 步停在各格的路径数」)。累计出界 ans = 2。
- 12开始第 2/2 步。新建空的 ndp,准备接收扩散结果;ans 当前 = 2。
- 13看 dp[0][1]=1(紫):它会把这 1 条路径分别推向上下左右四个邻居。
- 14从 (0,1) 往下到界内的 (1,1)(蓝),把 1 条路径累加进 ndp,ndp[1][1] 现为 1。
- 15从 (0,1) 往上走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 3。
- 16从 (0,1) 往右走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 4。
- 17从 (0,1) 往左到界内的 (0,0)(蓝),把 1 条路径累加进 ndp,ndp[0][0] 现为 1。
- 18看 dp[1][0]=1(紫):它会把这 1 条路径分别推向上下左右四个邻居。
- 19从 (1,0) 往下走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 5。
- 20从 (1,0) 往上到界内的 (0,0)(蓝),把 1 条路径累加进 ndp,ndp[0][0] 现为 2。
- 21从 (1,0) 往右到界内的 (1,1)(蓝),把 1 条路径累加进 ndp,ndp[1][1] 现为 2。
- 22从 (1,0) 往左走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 6。
- 23第 2 步扩散完毕,用 ndp 替换 dp(现在网格里的数是「走 2 步停在各格的路径数」)。累计出界 ans = 6。
- 24走满 2 步,累计出界路径 ans = 6。注意 dp 里还剩下的非零格,是「停在界内还没出去」的路径,不计入答案;只有真正跨出边界的才算。
⚠️ 容易写错的地方
✗ 错：原地在 dp 上扩散
✓ 对：用独立的 ndp 接收本步结果
同一步内若直接改 dp,会让刚更新的格子在本步内又被当成源重复扩散;必须用 ndp 隔离「这一步前」和「这一步后」
✗ 错：出界路径漏计或重复计
✓ 对：越界时把源格路径数一次性加进 ans
每条到达 (r,c) 的路径在这一步向某越界方向走,就是一条独立的出界路径,数量正是 dp[r][c],按方向逐次累加
✗ 错：相加不取模导致溢出
✓ 对：每次累加都对 1e9+7 取模,ans 用更宽整型暂存
路径数可指数级增长,C++/Java 的 int 会溢出;ans 与 ndp 都要边加边取模,C++ 用 long long、Java 用 long 暂存
完整代码（Python / C++ / Java）
Python
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
MOD = 10**9 + 7
dp = [[0] * n for _ in range(m)]
dp[startRow][startColumn] = 1
ans = 0
for _ in range(maxMove):
ndp = [[0] * n for _ in range(m)]
for r in range(m):
for c in range(n):
if dp[r][c]:
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n:
ans = (ans + dp[r][c]) % MOD
else:
ndp[nr][nc] = (ndp[nr][nc] + dp[r][c]) % MOD
dp = ndp
return ansC++
#include <vector>
using namespace std;
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
const int MOD = 1000000007;
vector<vector<int>> dp(m, vector<int>(n));
dp[startRow][startColumn] = 1;
long long ans = 0;
int dirs[5] = {1,0,-1,0,1};
for (int step = 0; step < maxMove; ++step) {
vector<vector<int>> ndp(m, vector<int>(n));
for (int r = 0; r < m; ++r) for (int c = 0; c < n; ++c) if (dp[r][c]) {
for (int d = 0; d < 4; ++d) {
int nr = r + dirs[d], nc = c + dirs[d+1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) ans = (ans + dp[r][c]) % MOD;
else ndp[nr][nc] = (ndp[nr][nc] + dp[r][c]) % MOD;
}
}
dp.swap(ndp);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
int MOD = 1_000_000_007;
int[][] dp = new int[m][n];
dp[startRow][startColumn] = 1;
long ans = 0;
int[] dirs = {1,0,-1,0,1};
for (int step = 0; step < maxMove; step++) {
int[][] ndp = new int[m][n];
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (dp[r][c] != 0) {
for (int d = 0; d < 4; d++) {
int nr = r + dirs[d], nc = c + dirs[d+1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) ans = (ans + dp[r][c]) % MOD;
else ndp[nr][nc] = (ndp[nr][nc] + dp[r][c]) % MOD;
}
}
dp = ndp;
}
return (int) ans;
}
}复杂度
时间
O(maxMove·m·n)
外层走 maxMove 步,每步遍历整张 m×n 网格、每格看 4 个方向(常数);整体 O(maxMove·m·n)
空间
O(m·n)
只需 dp 和 ndp 两张网格(滚动),O(m·n);不必存每一步的网格
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 出界的路径数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能用记忆化 DFS(从 (r,c,剩余步数) 出发)来做?+
可以,而且很自然。定义 dfs(r,c,move):从 (r,c) 出发还能走 move 步、能产生多少条出界路径。若 (r,c) 已越界返回 1(这条路径出界了);若 move 为 0 返回 0;否则对四个方向求和 dfs(nr,nc,move−1),用 memo[(r,c,move)] 缓存。它和本文的正推分层 DP 等价,状态都是「(位置, 剩余步数)」,复杂度同为 O(maxMove·m·n)。
为什么 dp 里剩下的非零格不计入答案?+
dp[r][c] 在走满 maxMove 步后表示「恰好停在界内 (r,c)、还没出界」的路径数。题目只统计「走出边界」的路径,这些停在界内的路径没有出界,自然不算。只有在某一步真正跨出网格的那一刻,才把对应路径数累加进 ans。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 出界的路径数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。