共计 1808 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 688. 骑士在棋盘上的概率 ，难度为 中等。
Tag :「线性 DP」
在一个 $n \times 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$
线性 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]$ 为「八连通」落点的概率之和，即有：
$$
f[i][j][p] = \sum {f[nx][ny][p – 1] \times \frac{1}{8}}
$$
代码：
class 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 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
