Medium

题目描述

在一个 n x n 的棋盘上，一个骑士从位置 (row, column) 开始，尝试进行恰好 k 次移动。行和列都是从 0 开始索引的，所以左上角的单元格是 (0, 0)，右下角的单元格是 (n - 1, n - 1)。

象棋骑士有八种可能的移动方式，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每当骑士要移动时，它都会从八种可能的移动中均匀随机选择一种（即使移动会让棋子移出棋盘）并移动到那里。

骑士继续移动，直到它走了恰好 k 步或离开了棋盘。

返回骑士在停止移动后仍留在棋盘上的概率。

示例 1：

输入: n = 3, k = 2, row = 0, column = 0
输出: 0.06250
解释: 有两种移动（到 (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

解题思路

这是一个典型的动态规划概率问题，我们需要计算骑士在 k 步移动后仍在棋盘上的概率。

核心思路：

  1. 状态定义：dp[i][r][c] 表示经过 i 步移动后，骑士在位置 (r, c) 的概率
  2. 状态转移：骑士有 8 种移动方式，每种移动的概率是 1/8。对于当前位置，我们需要计算从哪些位置可以一步到达当前位置
  3. 边界条件：初始位置的概率为 1，其他位置概率为 0
  4. 最终答案：所有棋盘内位置在第 k 步的概率之和

具体实现：

  • 使用三维 DP 数组，第一维表示步数，第二三维表示坐标
  • 也可以使用滚动数组优化空间复杂度，因为每一步只依赖于上一步的结果
  • 对于每个位置，遍历 8 个可能的前驱位置，如果前驱位置在棋盘内，则累加其贡献的概率

优化： 可以使用记忆化递归或者二维 DP + 滚动数组来优化空间复杂度。

代码实现

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<int>> directions = {{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}};
        
        // dp[i][j] represents probability at position (i,j)
        vector<vector<double>> dp(n, vector<double>(n, 0.0));
        dp[row][column] = 1.0;
        
        for (int step = 0; step < k; step++) {
            vector<vector<double>> next(n, vector<double>(n, 0.0));
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i][j] > 0) {
                        for (auto& dir : directions) {
                            int ni = i + dir[0];
                            int nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                next[ni][nj] += dp[i][j] / 8.0;
                            }
                        }
                    }
                }
            }
            dp = next;
        }
        
        double result = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result += dp[i][j];
            }
        }
        return result;
    }
};

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
        
        # dp[i][j] represents probability at position (i,j)
        dp = [[0.0] * n for _ in range(n)]
        dp[row][column] = 1.0
        
        for step in range(k):
            next_dp = [[0.0] * n for _ in range(n)]
            
            for i in range(n):
                for j in range(n):
                    if dp[i][j] > 0:
                        for di, dj in directions:
                            ni, nj = i + di, j + dj
                            if 0 <= ni < n and 0 <= nj < n:
                                next_dp[ni][nj] += dp[i][j] / 8.0
            
            dp = next_dp
        
        return sum(sum(row) for row in dp)

public class Solution {
    public double KnightProbability(int n, int k, int row, int column) {
        int[,] directions = {{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}};
        
        // dp[i,j] represents probability at position (i,j)
        double[,] dp = new double[n, n];
        dp[row, column] = 1.0;
        
        for (int step = 0; 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) {
                        for (int d = 0; d < 8; d++) {
                            int ni = i + directions[d, 0];
                            int nj = j + directions[d, 1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                next[ni, nj] += dp[i, j] / 8.0;
                            }
                        }
                    }
                }
            }
            dp = next;
        }
        
        double result = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result += dp[i, j];
            }
        }
        return result;
    }
}

var knightProbability = function(n, k, row, column) {
    const directions = [[-2,-1], [-2,1], [-1,-2], [-1,2], [1,-2], [1,2], [2,-1], [2,1]];
    
    // dp[i][j] represents probability at position (i,j)
    let dp = Array(n).fill().map(() => Array(n).fill(0));
    dp[row][column] = 1.0;
    
    for (let step = 0; step < k; step++) {
        const next = Array(n).fill().map(() => Array(n).fill(0));
        
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dp[i][j] > 0) {
                    for (const [di, dj] of directions) {
                        const ni = i + di;
                        const nj = j + dj;
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            next[ni][nj] += dp[i][j] / 8.0;
                        }
                    }
                }
            }
        }
        dp = next;
    }
    
    let result = 0.0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            result += dp[i][j];
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k × n² × 8) = O(k × n²)，需要进行 k 轮迭代，每轮遍历 n² 个位置，每个位置检查 8 个方向
空间复杂度O(n²)，使用两个 n×n 的二维数组存储当前状态和下一状态的概率分布

相关题目