🔥Easy Short 🔥Optimized🔥 C++ Solution With Explaination🔥
Explaination\n\nThe \'dir\' array is a 2D array representing the possible moves a knight can make on the chessboard. The knight can move to any of the 8 positio
# Explaination\n\nThe \'dir\' array is a 2D array representing the possible moves a knight can make on the chessboard. The knight can move to any of the 8 positions represented by the (row, col) pairs in the \'dir\' array.\n\nThe \'dp\' unordered map is used for memoization. It stores the calculated probabilities for different states (i.e., (k, row, column)) to avoid redundant calculations and improve the efficiency of the solution.\n\nThe \'solve\' function is a recursive function that calculates the probability of the knight staying within the board after making \'k\' moves starting from the given position (row, column). It returns the probability as a double value.\n\n- Base Cases:\n  - If the knight goes out of the board (i.e., row < 0, row >= n, column < 0, column >= n), return 0, as it\'s not a valid move.\n  - If \'k\' becomes 0, it means the knight has made all the moves, and it will stay within the board. So, return 1.\n\n- Memoization:\n  - Before calculating the probability for a specific state, check if it has already been calculated and stored in the \'dp\' map. If yes, return the stored value, avoiding redundant calculations.\n\n- Recursive Calculation:\n  - For each of the 8 possible moves, recursively call the \'solve\' function with \'k-1\' moves and the new position (row + dir[i][0], column + dir[i][1]).\n  - Calculate the sum of probabilities from all 8 possible moves.\n\n- Final Result:\n  - The final probability is the sum of probabilities obtained from all 8 possible moves, divided by 8 (since the knight has an equal probability of moving to any of the 8 positions).\n\n\n# Complexity\n- Time complexity: The time complexity of the \'solve\' function is O(k * 8) = O(k) because, for each of the 8 possible moves, it calls itself recursively. In the worst case, the \'solve\' function is called for each cell on the chessboard, which gives a total of n^2 calls. Therefore, the overall time complexity of the entire \'knightProbability\' function is **O(n^2 * k)**.\n\n- Space complexity: The maximum depth of the recursive call stack is equal to \'k\'. The \'dp\' unordered map stores the probabilities for each state, which has a maximum of O(n^2) unique states So, the space complexity due to the \'dp\' map is **O(n^2)**.\n\n# Code\n```\nclass Solution {\npublic:\n    int dir[8][8] = {{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};\n    unordered_map<string,double> dp;\n\n    double solve(int n,int k,int r, int c){\n        if(r<0  ||  r>=n  ||  c<0  ||  c>=n) return 0;\n        if(k==0) return 1;\n\n        string key= to_string(k)+"Leet"+ to_string(r)+ "Code"+ to_string(c);\n        if(dp.count(key)) return dp[key];\n\n        double prob=0;\n        for(int i=0;i<8;i++){\n            prob+= solve(n,k-1,r+dir[i][0],c+dir[i][1]);\n        }\n        return dp[key]=prob/8.0;\n    }\n\n    double knightProbability(int n, int k, int row, int column) {\n        return solve(n,k,row,column);\n    }\n};\n```
['Math', 'Dynamic Programming', 'Recursion', 'Probability and Statistics', 'C++']