出界的路径数
难度:
标签:
题目描述
给你一个大小为 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
代码结果
运行时间: 65 ms, 内存: 21.4 MB
/*
* 思路：
* 同样的动态规划思路，这里用 Java Stream API 简化代码。
* 我们通过流处理来更新 dp 数组，保留和传统实现相同的逻辑。
*/
import java.util.stream.IntStream;
public class Solution {
private static final int MOD = 1000000007;
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
int[][][] dp = new int[m][n][maxMove + 1];
dp[startRow][startColumn][0] = 1;
int count = 0;
for (int move = 1; move <= maxMove; move++) {
int[][][] temp = new int[m][n][maxMove + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = i;
int y = j;
IntStream.of(-1, 1).forEach(delta -> {
if (x + delta < 0 || x + delta >= m || y < 0 || y >= n) {
count = (count + dp[x][y][move - 1]) % MOD;
} else if (y + delta < 0 || y + delta >= n || x < 0 || x >= m) {
count = (count + dp[x][y][move - 1]) % MOD;
} else {
temp[x + delta][y][move] = (temp[x + delta][y][move] + dp[x][y][move - 1]) % MOD;
temp[x][y + delta][move] = (temp[x][y + delta][move] + dp[x][y][move - 1]) % MOD;
}
});
}
}
dp = temp;
}
return count;
}
}
解释
方法:
这个题解使用了记忆化递归的方法。首先判断如果最大移动次数为0，直接返回0。然后定义了一个递归函数countPaths，用来计算从当前位置(currX, currY)出发，在剩余的maxMove步内出界的路径数量。如果只剩下1步，那么只需判断当前位置是否在边界上，在的话就返回1，否则返回0。如果还有多步，就分别向上下左右四个方向递归调用countPaths，如果某个方向已经出界，则该方向的返回值为1。最后将四个方向的结果求和取模即可。主函数中调用countPaths(startRow, startColumn, maxMove)得到最终结果。
时间复杂度:
O(m * n * maxMove)
空间复杂度:
O(m * n * maxMove)
代码细节讲解
🦆
为什么在递归函数`countPaths`中，当只剩下1步时，是通过检查当前位置是否在边界上来决定是否返回1，这样的逻辑是否确保了所有可能的出界路径都被正确计算？
▷🦆
题解中提到，如果某个方向已经出界，则该方向的返回值为1。请问这种处理方式是否可能导致对某些路径的重复计数，特别是在接近边界的位置？
▷🦆
在没有任何移动时（maxMove为0），直接返回0的做法是否考虑了所有边界条件，例如如果开始位置就在边缘上是否应该有不同的返回值？
▷🦆
题解说明了使用`@cache`来避免重复计算，但如何确保缓存机制在这种多参数递归函数中有效提高性能？
▷相关问题
骑士在棋盘上的概率
在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。
象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
骑士继续移动，直到它走了 k 步或离开了棋盘。
返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。
示例 1：
输入: n = 3, k = 2, row = 0, column = 0 输出: 0.0625 解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。 在每一个位置上，也有两种移动可以让骑士留在棋盘上。 骑士留在棋盘上的总概率是0.0625。
示例 2：
输入: n = 1, k = 0, row = 0, column = 0 输出: 1.00000
提示:
1 <= n <= 250 <= k <= 1000 <= row, column <= n - 1