C++ Easy to understand | Recursion + Memoization
Approach\nTo solve this problem, we use a 3D DP (Dynamic Programming) approach to store the probabilities of different states of the knight. The three changing 
# Approach\nTo solve this problem, we use a 3D DP (Dynamic Programming) approach to store the probabilities of different states of the knight. The three changing states are k (the number of moves left), row (the current row of the knight), and col (the current column of the knight).\n\nThe base cases of the recursion are as follows:\n\nIf the knight goes outside the chessboard (row < 0 || col < 0 || row >= n || col >= n), the probability is 0.0, as it\'s impossible to stay on the board from there.\nIf the knight has made all k moves, the probability is 1.0, as there is no more chance to move.\nFor each state (k, row, col), we recursively explore all possible moves of the knight. We keep track of the probabilities of reaching different states and store them in the DP table to avoid redundant calculations. This way, we efficiently compute the probability of the knight staying on the board after making exactly k moves.\n\nAfter calculating the probabilities, we divide the final result by 8^k (as there are 8 possible moves at each step) to get the exact probability of the knight remaining on the board. \n\n\nI hope your knight will successfully explore all possibilities and remain on the chessboard with a high probability! \uD83D\uDE04\n\n# Complexity\n- Time complexity: $$O(k * n^2)$$\n\n- Space complexity: $$O(k * n^2)$$\n\n# Code\n```\n// Optimization with DP\n// As there are 3 changing states we will use 3D Dp\nclass Solution {\nprivate:\n    double solve(int n, int k, int row, int col, vector<vector<int>>&directions, vector<vector<vector<double>>>& dp){\n        if(row < 0 || col < 0 || row >= n || col >= n){\n            return 0.0;\n        }\n        if(k == 0){\n            return 1.0;\n        }\n        if(dp[k][row][col] != -1.0) return dp[k][row][col];\n\n        double ans = 0;\n        for(auto i: directions){\n            ans += solve(n, k-1, row+i[0], col + i[1], directions, dp);\n        }\n        return dp[k][row][col] =  ans;\n    }\npublic:\n    double knightProbability(int n, int k, int row, int column) {\n        vector<vector<vector<double>>>dp(k+1, vector<vector<double>>(n+1, vector<double>(n+1, -1.0)));\n        vector<vector<int>>directions = {\n            {1, 2}, {2,1}, {1, -2}, {2, -1},\n            {-1, -2}, {-2,-1}, {-1, 2}, {-2, 1},\n        };\n        double ans = solve(n, k, row, column, directions, dp);\n        double deno = pow(8,k);\n        double res = ans / deno;\n        return res;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']