Sponsored
Sponsored
In this approach, we utilize a 3D array `dp` where `dp[k][i][j]` represents the probability that the knight is on position `(i, j)` after making `k` moves. Initially, the knight is placed at `(row, column)`, so `dp[0][row][column] = 1`. For each move `k`, we calculate the probability of the knight being on each cell `(i, j)` by summing over probabilities of positions that can move to `(i, j)` in one knight move.
This involves iterating through each cell and updating the probabilities according to knight's possible moves.
Time Complexity: O(k * n^2), as each position on the board and each move is processed.
Space Complexity: O(k * n^2), for storing the DP states.
1function knightProbability(n, k, row, column) {
2 const dp = Array.from(Array(k + 1), () => Array.from(Array(n), () => Array(n).fill(0)));
3 const directions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]];
4 dp[0][row][column] = 1.0;
5
6 for (let m = 1; m <= k; m++) {
7 for (let i = 0; i < n; i++) {
8 for (let j = 0; j < n; j++) {
9 for (const [dx, dy] of directions) {
10 const ni = i + dx;
11 const nj = j + dy;
12 if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
13 dp[m][ni][nj] += dp[m - 1][i][j] / 8.0;
14 }
15 }
16 }
17 }
18 }
19
20 return dp[k].reduce((acc, row) => acc + row.reduce((rAcc, p) => rAcc + p, 0), 0);
21}The JavaScript code uses an array of arrays to emulate the 3D array used in other implementations. Probabilities are tracked for each square on the board over a given number of moves with adjustments from each possible knight step.
This approach leverages recursion along with memoization to optimize calculations. We define a recursive function to calculate the probability the knight remains within bounds after `k` moves. We utilize memoization to cache results of subproblems to avoid redundant calculations. If the knight's position ends within the board boundaries, it contributes to the final probability.
Time Complexity: O(k * n^2).
Space Complexity: O(k * n^2).
1 double[,,] memo = new double[101, 25, 25];
int[][] directions = new int[][] {
new int[] {2, 1}, new int[] {2, -1}, new int[] {-2, 1}, new int[] {-2, -1},
new int[] {1, 2}, new int[] {1, -2}, new int[] {-1, 2}, new int[] {-1, -2}};
public double KnightProbability(int n, int k, int row, int column) {
for (int i = 0; i <= 100; ++i)
for (int j = 0; j < 25; ++j)
for (int l = 0; l < 25; ++l)
memo[i, j, l] = -1;
return Recurse(n, k, row, column);
}
private double Recurse(int n, int k, int row, int column) {
if (row < 0 || row >= n || column < 0 || column >= n) return 0;
if (k == 0) return 1;
if (memo[k, row, column] != -1.0) return memo[k, row, column];
double prob = 0.0;
foreach (var dir in directions) {
prob += Recurse(n, k - 1, row + dir[0], column + dir[1]) / 8.0;
}
return memo[k, row, column] = prob;
}
}This C# solution adopts recursion alongside memoization to calculate and cache the knight's positional probabilities, maintaining efficiency by preventing recalculations of previously computed states.