↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

LeetCode-688 骑士在棋盘上的概率 #

Solution 1 #

概率递推, $dp[i][j][k]$ 代表起始位置为 $(i, j)$ , 移动 $k$ 次后仍在棋盘上的概率. 状态转移方程为: $$ dp[i][j][k] = \sum_{(x, y) \in \text{next}(i, j)} dp[x][y][k - 1] / 8 $$

代码如下:

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dirs = [[1, 2], [2, 1], [1, -2], [-2, 1], [-1, 2], [2, -1], [-1, -2], [-2, -1]]
        dp = [1 for _ in range(n * n)]
        for _ in range(k):
            dp0 = dp.copy()
            dp = [0 for _ in range(n * n)]
            for x in range(n):
                for y in range(n):
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < n:
                            dp[x * n + y] += dp0[nx * n + ny]
                    dp[x * n + y] /= 8
        return dp[row * n + column]