LeetCode 题解工作台
出界的路径数
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。 给你五个整数 m 、 n 、 maxMove 、 startRow 以及…
1
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义一个函数 $\textit{dfs}(i, j, k)$ 表示从坐标 $(i, j)$ 出发，还剩下 步可以移动的情况下，可以移出边界的路径数量。 在函数 $\textit{dfs}(i, j, k)$ 中，我们首先处理边界情况，如果当前坐标 $(i, j)$ 不在网格范围内，如果 $k \geq 0$，则返回 ，否则返回 。如果 $k \leq 0$，说明还在网格内，但是已经没有移动次…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。
示例 1：
输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0 输出：6
示例 2：
输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1 输出：12
提示：
1 <= m, n <= 500 <= maxMove <= 500 <= startRow < m0 <= startColumn < n
解题思路
方法一：记忆化搜索
我们定义一个函数 表示从坐标 出发，还剩下 步可以移动的情况下，可以移出边界的路径数量。
在函数 中，我们首先处理边界情况，如果当前坐标 不在网格范围内，如果 ，则返回 ，否则返回 。如果 ，说明还在网格内，但是已经没有移动次数了，返回 。接下来，我们遍历四个方向，移动到下一个坐标 ，然后递归调用 ，并将结果累加到答案中。
在主函数中，我们调用 ，即从起始坐标 出发，还剩下 步可以移动的情况下，可以移出边界的路径数量。
为了避免重复计算，我们可以使用记忆化搜索。
时间复杂度 ，空间复杂度 。其中 和 分别是网格的行数和列数，而 是可以移动的步数，本题中 。
class Solution:
def findPaths(
self, m: int, n: int, maxMove: int, startRow: int, startColumn: int
) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if not 0 <= i < m or not 0 <= j < n:
return int(k >= 0)
if k <= 0:
return 0
ans = 0
for a, b in pairwise(dirs):
x, y = i + a, j + b
ans = (ans + dfs(x, y, k - 1)) % mod
return ans
mod = 10**9 + 7
dirs = (-1, 0, 1, 0, -1)
return dfs(startRow, startColumn, maxMove)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(maxMove * m * n) because each move updates all grid positions. Space complexity can be O(m * n * maxMove) for full DP or optimized to O(m * n) using rolling arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Consider whether traversing every possible path recursively is feasible for larger maxMove values.
- question_mark
Expect hints towards state transition DP and memoization to handle repeated subproblems efficiently.
- question_mark
Watch for discussions on space optimization or iterative DP to improve performance for grids up to 50x50.
常见陷阱
外企场景- error
Failing to correctly count paths when the ball moves out of bounds immediately.
- error
Recomputing subproblems without memoization, causing exponential runtime.
- error
Ignoring modulo 10^9 + 7, which can cause integer overflow in large grids or many moves.
进阶变体
外企场景- arrow_right_alt
Compute paths when diagonal moves are also allowed, requiring adjustments to the DP state transitions.
- arrow_right_alt
Modify the problem to count paths of exactly maxMove moves instead of up to maxMove.
- arrow_right_alt
Return all unique sequences of moves leading out of the grid instead of just counts, which increases combinatorial complexity.