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.
1def knightProbability(n: int, k: int, row: int, column: int) -> float:
2 dp = [[[0.0] * n for _ in range(n)] for _ in range(k + 1)]
3 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 m in range(1, k + 1):
7 for i in range(n):
8 for j in range(n):
9 for d in directions:
10 ni, nj = i + d[0], j + d[1]
11 if 0 <= ni < n and 0 <= nj < n:
12 dp[m][ni][nj] += dp[m-1][i][j] / 8.0
13
14 return sum(dp[k][i][j] for i in range(n) for j in range(n))The Python code uses a list of lists to model the 3D `dp` array, storing probabilities for knight positions after `k` moves. The nested loops iterate through possible moves and positions to keep track of survival probabilities on the board.
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.