LeetCode-Go 题解576. Out of Boundary Paths —— 记忆化 DFS 求解出界路径数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 576. Out of Boundary Paths 题解 展开系统讲解如何统计一个在m × n网格中运动的球在最多maxMove次移动内移出网格边界的路径总数并要求结果对10⁹ 7取模。读完本文你将掌握暴力搜索为何会退化为4^n指数爆炸、如何用三维记忆化数组把复杂度降到O(m × n × maxMove)以及仓库中该题的完整 Go 实现与测试验证方式。题目描述在一个m x n的网格中有一个球。球初始位于[startRow, startColumn]。你可以把球移动到网格中四个相邻的单元格之一也可以移动出网格、穿过网格边界。你最多可以移动球maxMove次。给定五个整数m、n、maxMove、startRow、startColumn返回把球移出网格边界的路径数量。由于答案可能非常大请对10⁹ 7取模后返回。示例一Input: m 2, n 2, maxMove 2, startRow 0, startColumn 0 Output: 6在一个2 × 2的网格中球从(0, 0)出发最多移动 2 次共有 6 条路径可以移出边界。示例二Input: m 1, n 3, maxMove 3, startRow 0, startColumn 1 Output: 12在一个1 × 3的网格中球从(0, 1)出发最多移动 3 次共有 12 条路径可以移出边界。数据约束参数取值范围m, n1 m, n 50maxMove0 maxMove 50startRow0 startRow mstartColumn0 startColumn n题目大意给定一个m × n的网格和一个球。球的起始坐标为(i, j)你可以将球移到相邻的单元格内或者往上、下、左、右四个方向移动使球穿过网格边界。但最多只能移动N次。题目要求找出可以将球移出边界的路径数量。答案可能非常大返回结果对10⁹ 7取模后的值。注意一个细节所谓移出边界只要球在某一某一步之后越出网格范围这条路径就已经终结并计数为 1越界之后不会再继续走网格外没有可枚举的状态所以每一条合法的完整路径对应恰好一次越界事件。解题思路从暴力搜索到记忆化搜索为什么朴素 DFS 不可行最直接的想法是在球的每个位置向四个方向各遍历一步直到移动步数用完每当坐标越出网格就累计一次答案。这样暴力搜索的解空间大小是4^nn为maxMove。当maxMove取到约束上限 50 时4^50是一个天文数字显然无法在可接受时间内完成。问题出在大量重复子问题从不同的起点、经过不同的步数走到同一个格点时其后继路径的可能性完全相同但暴力搜索会把这些相同状态反复重新计算。记忆化用三维数组缓存已算过的状态优化思路便是增加记忆化memoization。用三维数组visited[x][y][step]记录位于(x, y)、还剩step次移动时能走出边界的路径数量。这样状态维度位置坐标(x, y)加上剩余步数step总共m × n × (maxMove 1)个状态每个状态的转移只依赖四个方向、步数减一的子状态转移代价为O(1)每个状态只计算一次首次访问时递归求解并缓存之后直接查表返回。加上记忆化以后仓库作者在 README 中注明该深搜解法的 runtime 可以 beat 100%。整个项目也以runtime beats 100%与100% test coverage作为目标见 README.md 的项目徽章声明测试覆盖由 gotest.sh 统一驱动。完整源码与逐行解析仓库中的核心实现位于 leetcode/0576.Out-of-Boundary-Paths/576. Out of Boundary Paths.go完整代码如下package leetcode var dir [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, } func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int { visited : make([][][]int, m) for i : range visited { visited[i] make([][]int, n) for j : range visited[i] { visited[i][j] make([]int, maxMove1) for l : range visited[i][j] { visited[i][j][l] -1 } } } return dfs(startRow, startColumn, maxMove, m, n, visited) } func dfs(x, y, maxMove, m, n int, visited [][][]int) int { if x 0 || x m || y 0 || y n { return 1 } if maxMove 0 { visited[x][y][maxMove] 0 return 0 } if visited[x][y][maxMove] 0 { return visited[x][y][maxMove] } res : 0 for i : 0; i 4; i { nx : x dir[i][0] ny : y dir[i][1] res (dfs(nx, ny, maxMove-1, m, n, visited) % 1000000007) } visited[x][y][maxMove] res % 1000000007 return visited[x][y][maxMove] }方向数组var dir [][]int{ {-1, 0}, // 上 {0, 1}, // 右 {1, 0}, // 下 {0, -1}, // 左 }四个方向的偏移量分别对应上、右、下、左。四个方向枚举的先后顺序不影响答案因为记忆化只关心状态值本身。记忆化数组的初始化visited : make([][][]int, m) for i : range visited { visited[i] make([][]int, n) for j : range visited[i] { visited[i][j] make([]int, maxMove1) for l : range visited[i][j] { visited[i][j][l] -1 } } }visited是一个三维数组维度为m × n × (maxMove 1)。所有元素初始化为-1题目保证任意合法路径数量都不小于 0因此用-1作为该状态尚未计算的哨兵值与真实计算结果天然区分。这里用一个显式三重循环完成-1填充也可以在make后直接遍历赋值效果等价。DFS 的三个终止条件dfs(x, y, maxMove, m, n, visited)表示从(x, y)出发、还剩maxMove步时移出边界的路径数。核心逻辑分三层第一层越界即得 1 分if x 0 || x m || y 0 || y n { return 1 }一旦坐标落在网格之外说明这一条路径已经成功走出了边界递归到这里直接返回1作为该分支的贡献。这正是题目计数语义的落点越界事件发生的当次移动即终结路径。第二层步数耗尽if maxMove 0 { visited[x][y][maxMove] 0 return 0 }如果仍在网格内但剩余步数为 0那么已经没有任何移动机会永远无法越界返回0。第三层命中缓存if visited[x][y][maxMove] 0 { return visited[x][y][maxMove] }这是记忆化的查表入口如果该状态此前已计算过缓存值非-1直接返回避免重复递归。状态转移与取模res : 0 for i : 0; i 4; i { nx : x dir[i][0] ny : y dir[i][1] res (dfs(nx, ny, maxMove-1, m, n, visited) % 1000000007) } visited[x][y][maxMove] res % 1000000007 return visited[x][y][maxMove]当前状态的值等于四个方向子状态之和。为了保证中间结果不溢出每次累加前先对子结果取1000000007的模累加完成后res % 1000000007再写入缓存并返回。这里注意取模的精度问题四个子状态各自都是(1e97)以内的数累加四次最坏约为4 × (1e97)仍在 Go 的int64 位平台安全范围内而若不做逐项取模深层递归中 res 会指数级膨胀必须全程模运算。状态定义与正确性验证这个记忆化 DFS 本质上就是一个自顶向下的动态规划。将其状态转移方程显式写出dp[x][y][k] dp[x-1][y][k-1] dp[x1][y][k-1] dp[x][y-1][k-1] dp[x][y1][k-1] (mod 1e97)边界条件为dp[越界坐标][k] 1任意剩余步数下越界即成功dp[网格内坐标][0] 0无步数可用则失败。可以看出递归实现与递推实现描述的是同一组状态只是求值顺序不同。仓库当前提供的实现是记忆化深搜版本读者若想改成自底向上的迭代 DP只需按k从小到大滚动更新即可二者复杂度一致。复杂度分析指标量级说明状态总数O(m × n × maxMove)位置m × n剩余步数0..maxMove共maxMove 1层单状态转移O(1)固定枚举 4 个方向时间总复杂度O(m × n × maxMove)每个状态只计算一次空间总复杂度O(m × n × maxMove)三维记忆化数组递归栈深度O(maxMove)最坏从起点一路递归到步数耗尽在题目约束m, n, maxMove ≤ 50下状态数最多约50 × 50 × 51 ≈ 127,500个计算量非常小这也是记忆化方案能在毫秒级返回答案、runtime 表现优异的原因。测试用例与运行验证仓库为本题配套了测试文件 leetcode/0576.Out-of-Boundary-Paths/576. Out of Boundary Paths_test.go采用表驱动table-driven风格组织用例qs : []question576{ { para576{2, 2, 2, 0, 0}, ans576{6}, }, { para576{1, 3, 3, 0, 1}, ans576{12}, }, }两个用例恰好对应题目给出的两个官方示例findPaths(2, 2, 2, 0, 0)期望输出6findPaths(1, 3, 3, 0, 1)期望输出12。本地验证方式需安装 Go 1.19项目模块信息见 go.mod# 单题测试 go test -v -run Test_Problem576 ./leetcode/0576.Out-of-Boundary-Paths/ # 全仓测试并生成覆盖率文件见 gotest.sh go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库根目录的 gotest.sh 脚本正是用第二种方式一次性对./leetcode/...下所有题解包执行带覆盖率的测试保证单一合法 coverage 文件输出这也是项目宣称100% test coverage的验证途径。测试中每个用例会打印输入与findPaths的实际输出便于核对示例结果。小结576 题的核心难点不在 DFS 本身而在于识别重复子问题并用记忆化消除指数爆炸朴素暴力枚举的代价是4^maxMove在maxMove 50时完全不可行定义三维状态(x, y, step)后全问题的状态数骤降至O(m × n × maxMove)三个关键边界条件——越界返回 1、步数耗尽返回 0、缓存命中直接查表——共同保证计数的正确性全程对10⁹ 7取模防止大数溢出。这份实现已在 LeetCode-Go 仓库中与测试用例一同沉淀读者可以直接参考 题解源码 与 测试文件 进行本地复现在此基础上把它改写成自底向上的迭代 DP也是一次不错的巩固练习。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考