Knight probability in chessboard

Dynamic Programming

56.9% acceptance

Feb 20, 2026

4021

494

On an n x n chessboard, a knight starts at (row, column) and makes exactly k moves uniformly at random. Return the probability it remains on the board.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn knight_probability(n: i32, k: i32, row: i32, column: i32) -> f64 {
    let n = n as usize;
    let moves = [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)];
    let mut dp = vec![vec![0.0f64; n]; n];
    dp[row as usize][column as usize] = 1.0;
    for _ in 0..k {
      let mut ndp = vec![vec![0.0f64; n]; n];
      for r in 0..n {
        for c in 0..n {
          if dp[r][c] == 0.0 { continue; }
          for &(dr, dc) in &moves {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < n as i32 && nc >= 0 && nc < n as i32 {
              ndp[nr as usize][nc as usize] += dp[r][c] / 8.0;
            }
          }
        }
      }
      dp = ndp;
    }
    dp.iter().flat_map(|row| row.iter()).sum()
  }
}