[LeetCode] 每日一题 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. 问题建模

这类问题可以使用动态规划（DP）来建模。我们可以将每一轮骑士在棋盘上的位置和步数作为状态来进行递推。考虑到骑士每一步的移动概率是均等的（1/8），我们可以用动态规划来计算骑士停留在棋盘上的概率。

2. 动态规划状态设计

• dp[step][i][j] 表示在经过 step 步后，骑士处于 (i, j) 位置的概率。

3. 状态转移

1. 初始化：对于 step = 0（即骑士刚开始的位置），骑士只能在 (row, column) 位置，概率为 1。其他位置的概率为 0。

2. 递推关系：

   • 对于每一步 step，我们考虑骑士从之前的 8 个可能位置移动过来的概率。即：dp[step][i][j] = sum(dp[step-1][prev_i][prev_j] / 8)，其中 (prev_i, prev_j) 是从 (i, j) 可以走到的任意位置。

3. 边界条件：如果骑士走出棋盘，概率为 0。

4. 优化和计算

由于动态规划会遍历所有的 k 步和棋盘位置，因此时间复杂度为 O(k * n^2)，是可以接受的。

代码实现

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        // dp[step][i][j] 表示走了 step 步后，骑士停留在 (i, j) 位置的概率
        double[][][] dp = new double[k + 1][n][n];
        
        // 骑士可以走的八个方向
        int[][] dirs = { { -2, -1 }, { -2, 1 }, { 2, -1 }, { 2, 1 }, { 1, 2 }, { 1, -2 }, { -1, -2 }, { -1, 2 } };
        
        // 初始状态：第 0 步时，骑士只在 (row, column) 位置上，概率为 1
        dp[0][row][column] = 1;
        
        // 动态规划递推
        for (int step = 1; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // 遍历骑士的 8 个可能的移动方向
                    for (int[] dir : dirs) {
                        int x = i + dir[0], y = j + dir[1];
                        
                        // 如果新位置在棋盘内，累加之前步数的概率
                        if (x >= 0 && x < n && y >= 0 && y < n) {
                            dp[step][i][j] += dp[step - 1][x][y] / 8;
                        }
                    }
                }
            }
        }
        // 返回 k 步后，骑士停留在 (row, column) 位置上的概率
        return dp[k][row][column];
    }
}

代码解析

1. 初始化 dp 数组：

我们使用一个三维数组 dp[step][i][j]，其中 step 表示当前的步数，i 和 j 分别表示骑士当前的位置。

• 初始时，dp[0][row][column] = 1，即在第 0 步时，骑士肯定在初始位置 (row, column)。

1. 状态转移：

   • 对于每个步骤 step，我们根据 8 个可能的移动方向，累加从上一轮位置到当前 (i, j) 位置的概率。

   • 每次骑士从一个位置移动到另一个位置的概率是 1/8，因为移动的选择是随机的。

2. 边界条件：

   • 如果骑士移动到棋盘外的位置，则该位置的概率为 0。

   • 如果在某个步骤后，骑士停留在棋盘内的某个位置，则 dp[step][i][j] 累加所有合法的移动路径。

3. 返回结果：

   • 最终返回 dp[k][row][column]，即骑士经过 k 步后，仍然留在棋盘上的概率。

时间复杂度和空间复杂度

• 时间复杂度：O(k * n^2)，需要遍历 k 步和每个位置 n * n，并对每个位置考虑 8 个方向的移动。

• 空间复杂度：O(k * n^2)，用于存储三维数组 dp。

总结

这道题目通过模拟骑士的随机移动过程，使用动态规划（DP）计算骑士在 k 步后停留在棋盘上的概率。我们通过三维数组来存储每一步骑士的概率，并通过状态转移公式递推到最终的结果。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。