LeetCode 688. 骑士在棋盘上的概率
目录
题目描述
题意分析
一个骑士站在 $n \times n$ 棋盘的指定格子上，要走恰好 k 步。每一步它在八个「日」字方向里等概率地挑一个走，哪怕这一步会踏出棋盘也照走不误；一旦踏出去就永远停在外面，不会再回来。要求的是走完 k 步之后骑士仍然留在棋盘内的概率。
有两点必须从题面里读准，读错了整道题都会跑偏。第一，是「恰好 k 步」而不是「最多 k 步」，中途留在盘上不算数。第二，出界不是被禁止的动作，而是一个概率为 $1/8$ 的合法分支，只不过它把这条路径判了死刑；因此每一步的八个方向都要平摊概率，不能把越界的方向剔除后在剩下的方向里重新均分。
约束是 $n \le 25$、$k \le 100$，格子最多六百多个，步数最多一百，两者相乘只有几万，这个体量提示我们可以把「步数」直接当成一个维度铺开算。另外 k 允许取 0，此时骑士一步没走，概率是 1，实现时不能漏掉这个入口。
解法：动态规划状态转移
核心思路
最直白的做法是把所有可能的走法枚举一遍：每步八个选择，k 步就是 $8^k$ 条路径，统计其中全程不出界的比例。k 取 100 时这个数字大到没有任何意义，连一步都跑不完。
瓶颈在于路径条数是指数级的，但骑士实际能站的位置只有 $n^2$ 种。大量不同的路径最后落在同一个格子上，而从这个格子继续往下走的行为完全不依赖它是怎么来的——只取决于它现在在哪、还要走几步。既然历史无关，就没有必要区分路径，只需要把落在同一格子上的概率合并起来。
由此定义状态：
dp[step][i][j]表示走完 step 步后，骑士全程没有出过界且此刻正停在格子 (i, j) 的概率。这个定义里「全程没出过界」是关键，它保证了出界的概率一旦流失就再也不会回到 dp 里。初始条件是dp[0][row][column] = 1，其余为 0，对应一步没走时骑士必然在起点。转移是把当前格子的概率均分给八个方向：对每个合法的 (ni, nj)，dp[step][ni][nj] += dp[step-1][i][j] / 8；落到界外的那部分概率不写进任何状态，自然就被丢弃了。最终答案是dp[k]这一整层所有格子的概率之和。由于第 step 层只依赖第 step - 1 层，不需要把整个三维数组开出来，用两块 $n \times n$ 的矩阵滚动即可。
解题步骤
- 开一个 $n \times n$ 的 dp 矩阵，把起点置为 1，其余为 0。这一层代表 step = 0，也就是「还没开始走」的状态，k 为 0 时直接对它求和就得到 1，边界自动成立。
- 外层循环 step 从 1 到 k，每轮先新建一个全零的 next 矩阵。必须写到新矩阵而不是原地累加，否则同一轮里刚被更新的格子会再次被当成起点参与本轮转移，等于让骑士在一步之内走了多次。
- 内层遍历所有格子，概率为 0 的格子直接跳过。这不只是性能优化，也让代码意图更清楚：只有可达状态才需要向外扩散。
- 对每个可达格子枚举八个方向，落在棋盘内的目标格累加
dp[i][j] / 8。除数固定是 8 而不是「合法方向的个数」，因为出界也是一次真实发生的选择，它带走的那 $1/8$ 概率就该消失。- 一轮结束后把 next 换成新的 dp，进入下一步。
- k 轮全部走完后，把 dp 矩阵所有格子求和返回。求和而不是读某一个格子，是因为题目只关心「是否还在盘上」，不关心停在哪里。
以
n = 3、k = 2、起点 (0, 0) 走一遍：初始 dp 里只有dp[0][0] = 1。第一步从 (0, 0) 出发枚举八个方向，只有 (1, 2) 和 (2, 1) 落在 $3 \times 3$ 的棋盘内，其余六个方向全部出界，因此 next 里next[1][2] = 1/8、next[2][1] = 1/8，这一层的概率总和是 $1/4$，恰好对应「第一步就出界」的概率是 $3/4$。第二步分别处理这两个格子：从 (1, 2) 出发，八个方向里只有 (2, 0) 和 (0, 0) 合法，各得到 $(1/8)/8 = 1/64$；从 (2, 1) 出发，八个方向里只有 (0, 2) 和 (0, 0) 合法，同样各得到 $1/64$。于是第二层中 (2, 0) 是 $1/64$、(0, 2) 是 $1/64$、(0, 0) 是 $1/64 + 1/64 = 2/64$。最后把整层求和得到 $4/64 = 0.0625$，与期望输出一致。
代码实现
// step=0 时起点概率为 1，其余为 0。
class Solution {
private static final int[][] DIRS = {
{1, 2}, {2, 1}, {-1, 2}, {-2, 1},
{1, -2}, {2, -1}, {-1, -2}, {-2, -1}
};
public double knightProbability(int n, int k, int row, int column) {
double[][] dp = new double[n][n];
dp[row][column] = 1.0;
for (int step = 1; step <= k; step++) {
double[][] next = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] == 0) {
continue;
}
for (int[] d : DIRS) {
int ni = i + d[0];
int nj = j + d[1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
next[ni][nj] += dp[i][j] / 8.0;
}
}
}
}
dp = next;
}
double total = 0.0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
total += dp[i][j];
}
}
return total;
}
}
// step=0 时起点概率为 1，其余为 0。
func knightProbability(n int, k int, row int, column int) float64 {
dirs := make([][2]int, 0, 8)
dirs = append(dirs, [2]int{1, 2}, [2]int{2, 1}, [2]int{-1, 2}, [2]int{-2, 1})
dirs = append(dirs, [2]int{1, -2}, [2]int{2, -1}, [2]int{-1, -2}, [2]int{-2, -1})
dp := make([][]float64, n)
for i := 0; i < n; i++ {
dp[i] = make([]float64, n)
}
dp[row][column] = 1.0
for step := 1; step <= k; step++ {
next := make([][]float64, n)
for i := 0; i < n; i++ {
next[i] = make([]float64, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if dp[i][j] == 0 {
continue
}
for _, d := range dirs {
ni := i + d[0]
nj := j + d[1]
if ni >= 0 && ni < n && nj >= 0 && nj < n {
next[ni][nj] += dp[i][j] / 8.0
}
}
}
}
dp = next
}
total := 0.0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
total += dp[i][j]
}
}
return total
}
复杂度分析
- 时间复杂度：$O(k \cdot n^2)$，共 k 轮，每轮遍历 $n^2$ 个格子，每个格子固定枚举 8 个方向，方向数是常数。在 $n = 25$、$k = 100$ 的上界下约为五十万次基本操作。
- 空间复杂度：$O(n^2)$，只保留当前层和下一层两块 $n \times n$ 的概率矩阵，不随 k 增长。
关键点总结
- 判断一个随机过程能不能上 DP，看的是「未来只依赖当前状态、与到达路径无关」这条性质；本题里骑士接下来怎么走只和位置与剩余步数有关，这就是把指数级路径压成 $O(k n^2)$ 状态的全部理由。
- 概率型 DP 的状态定义里必须写清「全程未出界」这类隐含前提，否则转移时会不自觉地把已经死掉的路径又捡回来。
- 每步固定除以 8 而不是除以合法方向数，是本题最核心的语义判断：出界是一个真实发生的分支，它带走的概率就该从系统里消失。
- 分层转移必须写到新数组，原地累加会让同一轮内的更新互相污染；凡是「按步数分层」的 DP 都要条件反射检查这一点。
- 面试视角：面试官常会用「为什么不能只在合法方向里均分」来试探你有没有真的理解概率模型，这是本题最高频的追问；能一句话解释清楚，基本就通过了。
- 面试视角：写完滚动数组后主动补一句「三维写法更好推导、二维滚动更省内存，两者转移完全一致」，能表明你是先想清楚状态再做的优化，而不是背下来一个二维模板。
易错点总结
- 错误写法：最后返回
dp[row][column]而不是整层求和：n = 3、k = 2、起点 (0, 0) → 只读到回到起点的 $2/64 = 0.03125$，而正确答案是整层之和 0.0625。- 错误写法：把除数写成当前格子合法方向的个数：
n = 3、k = 2、起点 (0, 0) → 第一步的两个合法方向各分到 $1/2$，概率永远不流失，最终返回 1。- 错误写法：不新建 next 矩阵，直接在 dp 上原地累加：
n = 3、k = 2→ 本轮刚写入的格子又被当成起点再扩散一次，等价于允许骑士在一步里连走多次，返回值偏大。- 错误写法：把 dp 初始化成全零后从 step = 1 开始填，而不是先把起点置 1：
k = 0→ 整个矩阵都是 0，返回 0，但一步没走时骑士必然在盘上，正确答案是 1。- 错误写法：越界判断写成
ni > n或nj > n：n = 3且目标落在下标 3 上 → 下标等于 n 被当成合法，直接数组越界；正确的比较是ni >= n。- 错误写法：方向数组少写几项，或误用国王、车的走法：
n = 3、k = 1、起点 (0, 0) → 合法落点从 2 个变成别的数量，第一步的存活概率就已经不是 $1/4$。- 错误写法：用整型累计合法路径条数，最后再除以 $8^k$：
k = 100→ $8^{100}$ 远超 64 位整型范围，计数一路溢出，结果完全无意义；概率题应当全程用浮点直接累加。- 错误写法：把「恰好 k 步」理解成「最多 k 步」，一旦某层概率之和不再变化就提前返回：任意 k 较大的输入 → 提前退出时留在盘上的概率远高于真实值，因为后续步数还会继续让骑士出界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 62. 不同路径 | 中等 | 只能右和下两个方向，求方案数，转移是两项相加 |
| 63. 不同路径 II | 中等 | 在 62 上加障碍格，障碍处状态强制置零 |
| 64. 最小路径和 | 中等 | 同样的网格但求最小代价，转移由求和改成取最小 |
| 120. 三角形最小路径和 | 中等 | 非矩形网格，自底向上推导能省掉边界判断 |
| 174. 地下城游戏 | 困难 | 必须倒着从终点推起，正推会因为血量下界失去最优子结构 |
| 931. 下降路径最小和 | 中等 | 按行滚动，每格从上一行的三个相邻列转移 |
| 1289. 下降路径最小和 II | 困难 | 禁止同列，需要预处理上一行的最小值与次小值把转移降到常数 |
| 1301. 最大得分的路径数目 | 困难 | 同时维护最大得分与达到该得分的方案数两个 DP |
| 1594. 矩阵的最大非负积 | 中等 | 因为有负数，必须同时维护最大积与最小积 |
| LCR 098. 不同路径 | 中等 | 与 62 同题，可用于练习一维滚动数组写法 |
| LCR 099. 最小路径和 | 中等 | 与 64 同题，重点是首行首列的初始化 |
| LCR 100. 三角形最小路径和 | 中等 | 与 120 同题，练习原地修改输入的空间优化 |
| 剑指 Offer 47. 礼物的最大价值 | 中等 | 求路径最大和，可直接在原矩阵上滚动一行 |