LeetCode 688. 骑士在棋盘上的概率

约 6 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 拼多多 猿辅导
标签
动态规划

题目描述

✅ 688. 骑士在棋盘上的概率

image-20260928224505655

image-20260928224505656

题意分析

骑士每一步都从八种走法中等概率选择一种，包括会走出棋盘的方向。一旦出界就停止，不能再回来。要求走满 k 步后仍在棋盘内的概率，不要求最终回到起点。

解法：动态规划状态转移

核心思路

[!blue]

用 dp[i][j] 表示已经走完当前步数、此前从未出界、且停在 (i, j) 的概率。这是相对于全部随机选择的概率，不是“已知还在棋盘上”时的位置占比。不同历史只要当前落点相同，下一步的选择规则就相同，可以把这些历史的概率合并在同一格。

起初一步都没走，起点概率为 1，其余位置为 0。每做一次转移，从当前格向八个方向分别分出 dp[i][j] / 8.0：落点合法就累加到 next，出界部分直接舍弃。即使只有少数方向合法，分母也仍是 8，不能把失去的概率重新分给合法方向。

一个落点可能由多个前驱到达，对应路径事件互不重叠，所以使用累加。每轮创建全零的 next，只读取上一轮的 dp，确保所有转移都恰好增加一步；本轮完成后再用 next 替换 dp。

经过 k 轮，dp 已经包含全部没有出界的路径。不同最终落点互不重叠，将所有格子的概率相加就是仍在棋盘内的总概率。出界路径从状态中消失，后续不会再参与转移。

解题步骤

  1. 准备八个移动方向，创建全零概率矩阵，将起点设为 1.0。
  2. 每一步新建全零的下一层矩阵 next。
  3. 遍历当前层所有非零状态，枚举八个落点；合法时执行 next[ni][nj] += dp[i][j] / 8.0。
  4. 本轮完成后令 dp = next，直到完成 k 步。
  5. 累加最后一层所有位置的概率并返回。

k = 0 时不执行转移，起点仍占全部概率，答案为 1。若某一层所有走法都出界，后续状态保持全零，答案自然为 0。

代码实现

// 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 := [][2]int{
        {1, 2},
        {2, 1},
        {-1, 2},
        {-2, 1},
        {1, -2},
        {2, -1},
        {-1, -2},
        {-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+1)n^2)$，包含初始化与最终求和。
  • 空间复杂度：$O(n^2)$，保留两层概率矩阵。

关键点总结

[!green]

  • 状态只记录仍在棋盘内的路径，矩阵总概率会因出界而减少。
  • 每条移动方向固定占八分之一，合法方向少不意味着重新均分。
  • 同层多来源贡献可以相加，不同步数的状态必须分层保存。

易错点总结

[!yellow]

  • 除以合法方向数量会保留本该流失的概率，计算成另一种随机过程。
  • 在 dp 中边读边写，会让同一步刚产生的概率又继续移动。
  • 下一层不清零，会把较早步数的概率混入本轮结果。
  • 最后只读取起点概率，得到的是回到起点的概率，会漏掉其他合法落点。

相似题目

题目 难度 关联与区别
576. 出界的路径数 中等 同样按步数推进网格状态，原题计出界路径，本题把每一步概率平均分到八个方向并丢弃出界部分。
935. 骑士拨号器 中等 同样枚举骑士合法移动，原题统计拨号路径数量，本题计算仍留在棋盘内的概率。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/60062286
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！