骑士在棋盘上的概率

难度: Medium

在一个 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

Submission

运行时间: 104 ms

内存: 16.2 MB

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp1 = [[0] * n for _ in range(n)]
        dp1[row][column] = 1
        all_perm = list(product([-2, 2], [-1, 1])) + list(product([-1, 1], [-2, 2]))
        for i in range(0, k):
            dp2 = [[0] * n for _ in range(n)]
            for p in range(n):
                for q in range(n):
                    if dp1[p][q] > 0:
                        for r,s in all_perm:
                            if p+r >= 0 and p+r < n and q+s >= 0 and q+s < n:
                                dp2[p+r][q+s] += 1/8*dp1[p][q]
            dp1 = dp2
        return sum([sum(i) for i in dp1])

Explain

此题解采用动态规划的方法。使用两个dp数组交替记录每个步数后的状态。初始化dp1数组，在初始位置(row, column)上的概率设置为1。接下来，对于每一步k，使用dp2数组计算基于dp1的结果。对于棋盘上每个可能的位置(p, q)，如果此位置在上一步有非零的概率，遍历所有可能的骑士移动，检查新位置是否还在棋盘内。如果在，则累加转移概率到dp2。每完成一步，dp1更新为dp2，继续下一轮迭代。最终，返回dp1中所有位置的概率和，即为骑士留在棋盘上的总概率。

时间复杂度: O(k * n^2)

空间复杂度: O(n^2)

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp1 = [[0] * n for _ in range(n)]  # dp1存储当前步的概率分布
        dp1[row][column] = 1  # 初始化起始位置的概率为1
        all_perm = list(product([-2, 2], [-1, 1])) + list(product([-1, 1], [-2, 2]))  # 骑士的所有可能移动
        for i in range(0, k):
            dp2 = [[0] * n for _ in range(n)]  # dp2用于计算下一步的概率分布
            for p in range(n):
                for q in range(n):
                    if dp1[p][q] > 0:  # 只处理有概率的位置
                        for r, s in all_perm:
                            if p+r >= 0 and p+r < n and q+s >= 0 and q+s < n:  # 检查新位置是否在棋盘内
                                dp2[p+r][q+s] += 1/8*dp1[p][q]  # 概率转移，每种移动的概率为1/8
            dp1 = dp2  # 更新dp1为下一步的结果
        return sum([sum(i) for i in dp1])  # 计算留在棋盘上的总概率

Explore

骑士在国际象棋中可以进行8种不同的移动（两个大步和一个小步的组合，方向可变）。因此，如果骑士在棋盘的某个位置且该位置可以向任意方向移动，则每种移动的概率都是相等的，即1/8。这是因为每一步骑士选择任意一种移动的可能性是均等的。

在动态规划中使用两个数组dp1和dp2交替更新的原因是避免在计算过程中覆盖或误用当前步骤的数据。如果只用一个数组，进行更新时新计算的概率值可能会影响同一步骤中后续的计算。使用两个数组可以确保在计算每一步时，来源的概率数据（dp1）保持不变，而结果的概率数据（dp2）是新计算出来的。这样可以清晰地区分每一步的数据，避免数据污染。

在迭代过程中，如果骑士的某次移动导致它落到棋盘外，这种情况下的概率确实会丢失，意味着这部分概率是骑士离开棋盘的概率。在最终计算骑士留在棋盘上的总概率时，只会累计那些依然在棋盘内的位置的概率。因此，移动到棋盘外的概率会被视为概率损失，这也符合问题的实际情况：计算骑士在棋盘上停留的概率。

当骑士的初始位置在棋盘的边缘或角落时，算法的表现确实与中间位置有所不同。由于边缘或角落的位置使得骑士的可移动选项减少（边缘通常有5种移动，角落只有2种），因此从这些位置开始的骑士更容易移动出棋盘，从而导致留在棋盘上的总概率较低。相比之下，中间位置周围没有限制，骑士有更高的概率保持在棋盘内。