#688

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Knight Probability in Chessboard

Calculate the probability that a knight remains on an n x n chessboard after making exactly k moves using dynamic programming.

dynamic programming

Problem Statement

Given an n x n chessboard, a knight starts at coordinates (row, column) and must make exactly k moves. Each move, the knight chooses one of eight possible L-shaped moves uniformly at random, even if the move would leave the board. Determine the probability that the knight remains on the board after completing all k moves. Rows and columns are 0-indexed, so (0,0) is the top-left corner.

Each knight move consists of two steps in one cardinal direction and one step orthogonally. For example, from (row, column), the knight can move to positions like (row+2, column+1), (row+1, column+2), etc. If a move takes the knight off the board, that path contributes zero to the total probability. Return the final probability as a floating-point number, reflecting the chance the knight never leaves the board in k moves.

Examples

Example 1

Input: n = 3, k = 2, row = 0, column = 0

Output: 0.06250

There are two moves (to (1,2), (2,1)) that will keep the knight on the board. From each of those positions, there are also two moves that will keep the knight on the board. The total probability the knight stays on the board is 0.0625.

Example 2

Input: n = 1, k = 0, row = 0, column = 0

Output: 1.00000

Example details omitted.

Constraints

1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1

Solution Approach

Define a 3D DP array

Create a DP array dp[step][i][j] representing the probability that the knight is on cell (i,j) after 'step' moves. Initialize dp[0][row][column] = 1 as the starting probability.

State transition for each move

For each step from 1 to k, update dp[step][i][j] by summing dp[step-1][ni][nj] / 8 over all valid positions (ni, nj) that can reach (i,j) in one knight move. Ignore moves that go off the board to avoid overcounting invalid paths.

Aggregate final probabilities

After filling the DP array for k steps, sum dp[k][i][j] for all board positions (i,j) to get the total probability the knight remains on the board. This ensures all valid paths are counted exactly once.

Complexity Analysis

Metric	Value
Time	O(k \cdot n^2)
Space	O(k \cdot n^2)

The time complexity is O(k * n^2) because each of the k steps updates every cell using up to 8 possible previous positions. Space complexity is also O(k * n^2), though it can be reduced to O(n^2) by alternating two 2D arrays for current and previous steps.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[h][i][j]$ to represent the probability that the knight remains on the board after taking $h$ steps starting from position $(i, j)$. The final answer is $f[k][\textit{row}][\textit{column}]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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]

Continue Practicing

#689 maximum sum of 3 non overlapping subarrays #691 stickers to spell word #678 valid parenthesis string