Leetcode Problem 688. Knight Probability in Chessboard

688. Knight Probability in Chessboard

Leetcode Solutions

Bottom-up Dynamic Programming with Optimized Space Complexity

  1. Define the 8 possible directions for the knight's moves.
  2. Initialize two 2D arrays prev_dp and curr_dp with zeros.
  3. Set prev_dp[row][column] to 1, representing the starting position of the knight.
  4. For each move from 1 to k, do the following:
    • For each cell (i, j) on the chessboard:
      • Set curr_dp[i][j] to 0.
      • For each of the 8 directions, calculate the previous cell (prev_i, prev_j).
      • If (prev_i, prev_j) is within the board, add prev_dp[prev_i][prev_j] / 8 to curr_dp[i][j].
    • Swap prev_dp and curr_dp.
  5. Sum up all values in prev_dp to get the total probability.
  6. Return the total probability.
UML Thumbnail

Top-down Dynamic Programming (Memoization)

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...