Knight Probability in Chessboard

Intuition

The key observation is that the probability of surviving depends only on the current cell and the number of moves still to be made, not on the path taken to get there. This lets us define dp(movesRemaining, r, c) as the probability of staying on the board when the knight is at (r, c) with movesRemaining moves left. Because every one of the eight knight jumps is equally likely, the probability at a cell is simply the average of the sub-probabilities of the eight destinations. Destinations that fall off the board contribute zero, which naturally encodes the 'lost forever' rule. The recursion bottoms out at movesRemaining == 0, where any on-board cell survives with probability 1. Memoizing on the triple avoids recomputing the same state across overlapping subtrees.

Algorithm walkthrough

1. 1If the current cell is off the board, return probability 0 because the knight has already been lost.
2. 2If no moves remain and the cell is on the board, return probability 1.
3. 3Otherwise generate the eight knight destinations from (r, c) and recurse with movesRemaining reduced by one.
4. 4Sum the eight returned sub-probabilities and divide by 8 to get the average, since every move is equally likely.
5. 5Cache the result for (movesRemaining, r, c) so repeated states are answered in constant time.
6. 6Return dp(k, row, column) as the final answer for the starting position.

Implementation

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
                 (1, -2), (1, 2), (2, -1), (2, 1)]
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(moves_left: int, r: int, c: int) -> float:
            if r < 0 or r >= n or c < 0 or c >= n:
                return 0.0
            if moves_left == 0:
                return 1.0
            total = 0.0
            for dr, dc in moves:
                total += dp(moves_left - 1, r + dr, c + dc)
            return total / 8.0

        return dp(k, row, column)