C++ ✅ Beats 99% ⚡ Easy Solution with Explanation ✅ 3D DP Memoization ❤️‍🔥
Intuition\nThe problem can be solved using a recursive approach with memoization. We can start with the given position of the knight and simulate all possible m
# Intuition\nThe problem can be solved using a recursive approach with memoization. We can start with the given position of the knight and simulate all possible moves it can make while keeping track of the probability of staying on the board at each step. The knight has eight possible moves it can make, and at each move, it has an equal probability of choosing any of those moves.\n\n# Approach\n\nCreate a 3D array `dp` to memoize the calculated probabilities for each position and remaining moves.\n\nDefine the `dirs` array to store the eight possible moves a knight can make.\n\nLet\'s define the recursive function `find(row, col, move)` as the probability of the knight staying on the board after making `move` moves starting from position `(row, col)`.\n\n\nThe recursive formula for `find(row, col, move)` is as follows:\n\n- If the knight is already off the board, return probability 0:\n`if (row < 0 or row >= n or col < 0 or col >= n) return 0`\n\n- If no more moves are left (move == 0), return probability 1, as the knight is already on the board:\n`if (move == 0) return 1`\n\n- If the probability for the current position and remaining moves is already calculated, return the precalculated value to avoid redundant computations:\n`if (dp[row][col][move]) return dp[row][col][move]`\n\n- Otherwise, calculate the total probability `prob` for the current position:\n````\ndouble prob = 0.0;\nfor(int i=0; i<8; i++) {\n    prob += find(row + dirs[i][0], col + dirs[i][1], n, move - 1) / 8.0;\n}\n````\n\n- The probability calculation code iterates over all eight possible moves that a knight can make. For each move, it calls the recursive function `find` with the new position `(row + dirs[i][0], col + dirs[i][1])` and decrements the remaining moves by one `(move - 1)`.\n\n- The `find` function returns the probability of staying on the board after making the given number of moves from the new position. The probabilities returned from all eight possible moves are added together and divided by 8.0 to calculate the average probability. This average probability represents the probability of staying on the board after making one move from the current position.\n\n\n- Store the probability of current position with remaining moves in `dp` and return the `prob`\n\n# Complexity\n- Time complexity: $$O(n*n*k)$$\n- Space complexity: $$O(n*n*k) + O(k)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int dirs[8][2] = {{2,-1}, {2, 1}, {-2,-1}, {-2, 1}, {1, -2}, {1, 2}, {-1, -2}, {-1, 2}}; \n    double dp[30][30][105];\n\n    double find(int row, int col, int n, int move) {\n        if(row < 0 || row >= n || col < 0 || col >= n) return 0;\n        if(move == 0) return 1;\n\n        if(dp[row][col][move]) return dp[row][col][move];\n\n        double prob = 0.0;\n        for(int i=0; i<8; i++) {\n            prob += find(row + dirs[i][0], col + dirs[i][1], n, move - 1) / 8.0;\n        }\n        return dp[row][col][move] = prob;\n    }\n    double knightProbability(int n, int k, int row, int col) {\n        memset(dp, 0, sizeof(dp));\n        return find(row, col, n, k);\n    }\n};\n```\n\n# Reminder\n\nIf you like this solution, please upvote and share with your friends.
['Dynamic Programming', 'C++']