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.
1public class Solution {
2 public double KnightProbability(int n, int k, int row, int column) {
3 double[,,] dp = new double[k + 1, n, n];
4 int[,] directions = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } };
5 dp[0, row, column] = 1.0;
6
7 for (int m = 1; m <= k; m++) {
8 for (int i = 0; i < n; i++) {
9 for (int j = 0; j < n; j++) {
10 for (int d = 0; d < 8; d++) {
11 int ni = i + directions[d, 0];
12 int nj = j + directions[d, 1];
13 if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
14 dp[m, ni, nj] += dp[m-1, i, j] / 8.0;
15 }
16 }
17 }
18 }
19 }
20
21 double result = 0.0;
22 for (int i = 0; i < n; i++) {
23 for (int j = 0; j < n; j++) {
24 result += dp[k, i, j];
25 }
26 }
27 return result;
28 }
29}The C# implementation uses a three-dimensional array to store probabilities for positions after each move. It iterates over moves and directions within the array to calculate updated probability values.
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).
1using namespace std;
vector<vector<vector<double>>> memo(101, vector<vector<double>>(25, vector<double>(25, -1.0)));
vector<pair<int, int>> directions{{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
// Recursive memoization function
double recurse(int n, int k, int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= n) return 0;
if (k == 0) return 1;
if (memo[k][i][j] != -1.0) return memo[k][i][j];
double prob = 0.0;
for (auto &dir : directions) {
int ni = i + dir.first;
int nj = j + dir.second;
prob += recurse(n, k - 1, ni, nj) / 8.0;
}
return memo[k][i][j] = prob;
}
double knightProbability(int n, int k, int row, int column) {
return recurse(n, k, row, column);
}The C++ code employs recursive calls with memoization to compute the knight's probability, leveraging cached results in `memo` to prevent repeated calculations.