友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
576. 出界的路径数
给你一个大小为 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 <= 50 -
0 <= maxMove <= 50 -
0 <= startRow < m -
0 <= startColumn < n
思路分析
深度优先遍历会超时，因为会有重复计算。加一个备忘录，可以减少不必要的重复计算，提高效率。
看题解也可以用动态规格来做。下次试试。
另外，能用备忘录的题目，一般也都可以用动态规划来求解。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-03-22 15:52:29
*/
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
Map<Integer, Integer> memo = new HashMap<>();
return dfs(m, n, maxMove, startRow, startColumn, memo);
}
private int dfs(int m, int n, int move, int row, int column, Map<Integer, Integer> memo) {
int MOD = 1_000_000_007;
if (row < 0 || m <= row
|| column < 0 || n <= column) {
return 1;
}
if (move <= 0) {
return 0;
}
Integer key = 10000 * move + 100 * row + column;
if (memo.containsKey(key)) {
return memo.get(key);
}
int next = move - 1;
// 上
int result = dfs(m, n, next, row - 1, column, memo);
// 下
result += dfs(m, n, next, row + 1, column, memo);
result %= MOD;
// 左
result += dfs(m, n, next, row, column - 1, memo);
result %= MOD;
// 右
result += dfs(m, n, next, row, column + 1, memo);
result %= MOD;
memo.put(key, result);
return result;
}