LC 688. 骑士在棋盘上的概率
题目描述
这是 LeetCode 上的 688. 骑士在棋盘上的概率 ,难度为 中等。
在一个 $n \times n$ 的国际象棋棋盘上,一个骑士从单元格 $(row, column)$ 开始,并尝试进行 $k$ 次移动。行和列是 从 $0$ 开始 的,所以左上单元格是 $(0,0)$ ,右下单元格是 $(n - 1, n - 1)$ 。
象棋骑士有 $8$ 种可能的走法,如下图所示。每次移动在基本方向上是两个单元格,然后在正交方向上是一个单元格。
每次骑士要移动时,它都会随机从 $8$ 种可能的移动中选择一种(即使棋子会离开棋盘),然后移动到那里。
骑士继续移动,直到它走了 $k$ 步或离开了棋盘。
返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。
示例 1:1
2
3
4
5
6
7输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2),(2,1))可以让骑士留在棋盘上。
在每一个位置上,也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。
示例 2:1
2
3输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000
提示:
- $1 <= n <= 25$
- $0 <= k <= 100$
- $0 <= row, column <= n$
线性 DP
定义 $f[i][j][p]$ 为从位置 $(i, j)$ 出发,使用步数不超过 $p$ 步,最后仍在棋盘内的概率。
不失一般性考虑 $f[i][j][p]$ 该如何转移,根据题意,移动规则为「八连通」,对下一步的落点 $(nx, ny)$ 进行分情况讨论即可:
- 由于计算的是仍在棋盘内的概率,因此对于 $(nx, ny)$ 在棋盘外的情况,无须考虑;
- 若下一步的落点 $(nx, ny)$ 在棋盘内,其剩余可用步数为 $p - 1$,则最后仍在棋盘的概率为 $f[nx][ny][p - 1]$,则落点 $(nx, ny)$ 对 $f[i][j][p]$ 的贡献为 $f[nx][ny][p - 1] \times \frac{1}{8}$,其中 $\frac{1}{8}$ 为事件「从 $(i, j)$ 走到 $(nx, ny)$」的概率(八连通移动等概率发生),该事件与「到达 $(nx, ny)$ 后进行后续移动并留在棋盘」为相互独立事件。
最终的 $f[i][j][p]$ 为「八连通」落点的概率之和,即有:
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
int[][] dirs = new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};
public double knightProbability(int n, int k, int row, int column) {
double[][][] f = new double[n][n][k + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
f[i][j][0] = 1;
}
}
for (int p = 1; p <= k; p++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int[] d : dirs) {
int nx = i + d[0], ny = j + d[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
f[i][j][p] += f[nx][ny][p - 1] / 8;
}
}
}
}
return f[row][column][k];
}
}
- 时间复杂度:令某个位置可联通的格子数量 $C = 8$,复杂度为 $O(n^2 \times k \times C)$
- 空间复杂度:$O(n^2 \times k)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.688
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!