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.
1#include <stdio.h>
2
3#define MAX 25
4
5double knightProbability(int n, int k, int row, int column) {
6 double dp[k+1][MAX][MAX];
7 int directions[8][2] = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
8
9 // Initialize
10 memset(dp, 0, sizeof(dp));
11 dp[0][row][column] = 1;
12
13 // Fill DP table
14 for (int m = 1; m <= k; ++m) {
15 for (int i = 0; i < n; ++i) {
16 for (int j = 0; j < n; ++j) {
17 if (dp[m-1][i][j] > 0) {
18 for (int d = 0; d < 8; ++d) {
19 int ni = i + directions[d][0];
20 int nj = j + directions[d][1];
21 if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
22 dp[m][ni][nj] += dp[m-1][i][j] / 8.0;
23 }
24 }
25 }
26 }
27 }
28 }
29
30 // Sum up probabilities
31 double result = 0.0;
32 for (int i = 0; i < n; ++i) {
33 for (int j = 0; j < n; ++j) {
34 result += dp[k][i][j];
35 }
36 }
37 return result;
38}The code initializes a 3D dynamic array `dp` for storing the probabilities of being on each board position `(i, j)` after `k` moves. We iterate through each move and potential knight positions, updating probabilities based on possible knight moves.
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
C implementation uses recursion with memoization to solve the problem. The `memo` table caches results for specific `(i, j, k)` states to avoid redundant computations.