What is the best approach for Knight Probability in Chessboard problem?

State transition dynamic programming is optimal, tracking probability for each cell at each move step and aggregating results.

How do I handle moves that go off the chessboard?

Any move that leaves the board contributes zero to probability; DP only sums over valid in-board moves.

Can space usage be optimized in this DP solution?

Yes, by storing only the previous and current step 2D arrays instead of a full k-layer 3D array.

Why is recursion without memoization inefficient here?

Because the number of paths grows exponentially with k, naive recursion will timeout for larger k values.

What is the time complexity of this approach?

The time complexity is O(k * n^2) since each step updates every cell considering up to 8 possible moves.

#688

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

骑士在棋盘上的概率

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是从 0 开始的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在…

动态规划

题目描述

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[h][i][j]$ 表示骑士从 $(i, j)$ 位置出发，走了 $h$ 步以后还留在棋盘上的概率。那么最终答案就是 $f[k][\textit{row}][\textit{column}]$ 。

当 $h=0$ 时，骑士一定在棋盘上，概率为 $1$ ，即 $f[0][i][j]=1$ 。

当 $h \gt 0$ 时，骑士在 $(i, j)$ 位置上的概率可以由其上一步的 $8$ 个位置上的概率转移得到，即：

f[h][i][j] = \sum_{x, y} f[h - 1][x][y] \times \frac{1}{8}

其中 $(x, y)$ 是从 $(i, j)$ 位置可以走到的 $8$ 个位置中的一个。

最终答案即为 $f[k][\textit{row}][\textit{column}]$ 。

时间复杂度 $O(k \times n^2)$ ，空间复杂度 $O(k \times n^2)$ 。其中 $k$ 和 $n$ 分别是给定的步数和棋盘大小。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        f = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        for i in range(n):
            for j in range(n):
                f[0][i][j] = 1
        for h in range(1, k + 1):
            for i in range(n):
                for j in range(n):
                    for a, b in pairwise((-2, -1, 2, 1, -2, 1, 2, -1, -2)):
                        x, y = i + a, j + b
                        if 0 <= x < n and 0 <= y < n:
                            f[h][i][j] += f[h - 1][x][y] / 8
        return f[k][row][column]

speed

复杂度分析

指标	值
时间	O(k \cdot n^2)
空间	O(k \cdot n^2)

psychology

面试官常问的追问

外企场景

question_mark
Check if you can optimize space by storing only two layers instead of k layers.
question_mark
Watch for edge cases where the knight starts near the border or with k = 0.
question_mark
Clarify whether the knight moves off the board contribute zero probability and adjust DP accordingly.

warning

常见陷阱

外企场景

error
Incorrectly counting moves that leave the board, inflating the probability.
error
Failing to initialize the starting cell probability correctly at step 0.
error
Using recursive solutions without memoization, causing exponential time.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the expected number of moves a knight can make before leaving the board instead of exact probability.
arrow_right_alt
Change the board size dynamically and query probabilities for multiple starting positions efficiently.
arrow_right_alt
Restrict knight moves to a subset of allowed moves and calculate the probability of staying on board.

help

常见问题

外企场景

继续练习

#689 三个无重叠子数组的最大和 #691 贴纸拼词 #678 有效的括号字符串