题目描述
思路解析动画文字版
记住「每步把 dp 往四周扩散:界内进 ndp、越界进 ans」,下面逐步套它。
初始 dp 网格:只有起点 (0,0) 是 1(高亮),其余为 0。ans 从 0 开始累计出界路径。
开始第 1/2 步。新建空的 ndp,准备接收扩散结果;ans 当前 = 0。
看 dp[0][0]=1(紫):它会把这 1 条路径分别推向上下左右四个邻居。
从 (0,0) 往下到界内的 (1,0)(蓝),把 1 条路径累加进 ndp,ndp[1][0] 现为 1。
从 (0,0) 往上走出网格了,这 1 条路径正好在第 1 步出界,计入 ans,现 ans = 1。
从 (0,0) 往右到界内的 (0,1)(蓝),把 1 条路径累加进 ndp,ndp[0][1] 现为 1。
从 (0,0) 往左走出网格了,这 1 条路径正好在第 1 步出界,计入 ans,现 ans = 2。
第 1 步扩散完毕,用 ndp 替换 dp(现在网格里的数是「走 1 步停在各格的路径数」)。累计出界 ans = 2。
开始第 2/2 步。新建空的 ndp,准备接收扩散结果;ans 当前 = 2。
看 dp[0][1]=1(紫):它会把这 1 条路径分别推向上下左右四个邻居。
从 (0,1) 往下到界内的 (1,1)(蓝),把 1 条路径累加进 ndp,ndp[1][1] 现为 1。
从 (0,1) 往上走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 3。
从 (0,1) 往右走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 4。
从 (0,1) 往左到界内的 (0,0)(蓝),把 1 条路径累加进 ndp,ndp[0][0] 现为 1。
看 dp[1][0]=1(紫):它会把这 1 条路径分别推向上下左右四个邻居。
从 (1,0) 往下走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 5。
从 (1,0) 往上到界内的 (0,0)(蓝),把 1 条路径累加进 ndp,ndp[0][0] 现为 2。
从 (1,0) 往右到界内的 (1,1)(蓝),把 1 条路径累加进 ndp,ndp[1][1] 现为 2。
从 (1,0) 往左走出网格了,这 1 条路径正好在第 2 步出界,计入 ans,现 ans = 6。
第 2 步扩散完毕,用 ndp 替换 dp(现在网格里的数是「走 2 步停在各格的路径数」)。累计出界 ans = 6。
走满 2 步,累计出界路径 ans = 6。注意 dp 里还剩下的非零格,是「停在界内还没出去」的路径,不计入答案;只有真正跨出边界的才算。
边界:0 步为 0;1×1 一步为 4;大步数靠取模。
两个延伸:可记忆化 DFS(位置,剩余步数)等价;停界内的路径不算出界。
参考代码
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 ans复杂度
- 时间：O(maxMove·m·n)，外层走 maxMove 步,每步遍历整张 m×n 网格、每格看 4 个方向(常数);整体 O(maxMove·m·n)
- 空间：O(m·n)，只需 dp 和 ndp 两张网格(滚动),O(m·n);不必存每一步的网格
易错点
面试追问把动画讲成自己的话
追问能不能用记忆化 DFS(从 (r,c,剩余步数) 出发)来做?
追问为什么 dp 里剩下的非零格不计入答案?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
两个字符串的删除操作
LeetCode 583 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题