友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
688. 骑士在棋盘上的概率
在一个 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 <= 25 -
0 <= k <= 100 -
0 <= row, column <= n - 1
思路分析
竟然没想到是动态规划！我还以为是深度优先搜索，还尝试遍历所有可能情况。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-16 23:24:19
*/
private static final int[][] DIRS = {{2, 1}, {1, 2},
{-1, 2}, {-2, 1,}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
public double knightProbability(int n, int k, int row, int column) {
double[][][] memo = new double[k + 1][n][n];
return dfs(n, k, row, column, memo);
}
private double dfs(int n, int k, int row, int column, double[][][] memo) {
if (row < 0 || row >= n || column < 0 || column >= n) {
return 0;
}
if (k == 0) {
return 1;
}
if (memo[k][row][column] > 0) {
return memo[k][row][column];
}
double result = 0;
for (int[] d : DIRS) {
result += dfs(n, k - 1, row + d[0], column + d[1], memo);
}
return memo[k][row][column] = result / DIRS.length;
}