101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Dynamic Programming (3D) - Complex approach
  2. Dynamic Programming with Space Optimization - Complex approach

Approach 1: Dynamic Programming (3D)

The key insight for solving this problem is to use dynamic programming to calculate the probability of the knight being at each cell after a certain number of moves.

Let's define a 3D DP array dp[moves][row][col] where:

  • moves represents the number of moves made so far (from 0 to k)
  • row represents the current row (from 0 to n-1)
  • col represents the current column (from 0 to n-1)

The value dp[moves][row][col] represents the probability of the knight being at cell (row, col) after making moves moves.

The base case is:

  • dp[0][startRow][startCol] = 1.0 (the knight is at the starting position with 100% probability after 0 moves)

For the recurrence relation, we need to consider all possible previous positions that can lead to the current position through a valid knight move.

Let's define the possible knight moves:

  • (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)

For each cell (row, col) and each move m, we calculate:

dp[m][row][col] = sum(dp[m-1][prevRow][prevCol] / 8.0) for all valid previous positions (prevRow, prevCol)

We divide by 8.0 because the knight has 8 possible moves, and each move is chosen with equal probability (1/8).

The final probability is the sum of dp[k][row][col] for all cells (row, col) on the board.

Algorithm:

  1. Define the possible knight moves: (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1).
  2. Initialize a 3D DP array dp of size (k+1) × n × n, where dp[moves][row][col] represents the probability of the knight being at cell (row, col) after making moves moves.
  3. Set the base case: dp[0][startRow][startCol] = 1.0.
  4. For each move m from 1 to k:
  5. a. For each cell (row, col) on the board:
  6. i. For each possible knight move (dr, dc):
  7. 1. Calculate the previous position: prevRow = row - dr, prevCol = col - dc.
  8. 2. If the previous position is valid (on the board), then dp[m][row][col] += dp[m-1][prevRow][prevCol] / 8.0.
  9. Calculate the final probability as the sum of dp[k][row][col] for all cells (row, col) on the board.

Time Complexity:

O(k * n^2)

We need to compute the DP values for each move, each row, and each column. There are k moves, n rows, and n columns, and for each cell, we consider 8 possible knight moves, which is a constant factor.

Space Complexity:

O(k * n^2)

We use a 3D DP array of size (k+1) × n × n to store the probability of the knight being at each cell after each move.

Approach 2: Dynamic Programming with Space Optimization

We can optimize the space complexity by observing that to compute the DP values for the current move, we only need the DP values for the previous move.

Instead of using a 3D DP array, we can use two 2D arrays: curr and prev, each of size n × n, to store the DP values for the current move and the previous move, respectively.

After computing the DP values for the current move, we update prev to curr and reset curr for the next move.

The recurrence relation remains the same:

curr[row][col] = sum(prev[prevRow][prevCol] / 8.0) for all valid previous positions (prevRow, prevCol)

The final probability is the sum of prev[row][col] for all cells (row, col) on the board after the last move.

Algorithm:

  1. Define the possible knight moves: (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1).
  2. Initialize two 2D arrays prev and curr, each of size n × n, where prev[row][col] represents the probability of the knight being at cell (row, col) after the previous move.
  3. Set the base case: prev[startRow][startCol] = 1.0.
  4. For each move m from 1 to k:
  5. a. Reset curr to all zeros.
  6. b. For each cell (row, col) on the board:
  7. i. For each possible knight move (dr, dc):
  8. 1. Calculate the previous position: prevRow = row - dr, prevCol = col - dc.
  9. 2. If the previous position is valid (on the board), then curr[row][col] += prev[prevRow][prevCol] / 8.0.
  10. c. Update prev = curr.
  11. Calculate the final probability as the sum of prev[row][col] for all cells (row, col) on the board.

Time Complexity:

O(k * n^2)

The time complexity remains the same as the 3D DP approach, as we still need to compute the DP values for each move, each row, and each column.

Space Complexity:

O(n^2)

We only use two 2D arrays of size n × n, which is a significant improvement over the 3D DP approach.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function knightProbability(n, k, row, column):
    // Define the possible knight moves
    directions = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
 
    // Initialize DP array
    dp = new 3D array of size (k+1) × n × n, initialized with 0.0
 
    // Base case
    dp[0][row][column] = 1.0
 
    // Fill DP array
    for m from 1 to k:
        for r from 0 to n-1:
            for c from 0 to n-1:
                for each (dr, dc) in directions:
                    prevRow = r - dr
                    prevCol = c - dc
                    if 0 <= prevRow < n and 0 <= prevCol < n:
                        dp[m][r][c] += dp[m-1][prevRow][prevCol] / 8.0
 
    // Calculate the final probability
    result = 0.0
    for r from 0 to n-1:
        for c from 0 to n-1:
            result += dp[k][r][c]
 
    return result
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone