✅beats 100% - 2 appproach  || java || c++ 🔥 ||  with explanation || backtracking 🔥 🔥
understnading the poroblem : \nThe problem describes a scenario where a chess knight is placed on an n x n chessboard and attempts to make exactly k moves. The 
# understnading the poroblem : \nThe problem describes a scenario where a chess knight is placed on an n x n chessboard and attempts to make exactly k moves. The knight has eight possible moves it can make at each step, and it chooses one of these moves uniformly at random.\n\nThe chessboard is represented as an n x n grid, where the rows and columns are 0-indexed. The top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).\n\n##### The eight possible moves of the knight are as follows:\n\n- Two cells up and one cell to the right.\n- 2 Two cells up and one cell to the left.\n- Two cells down and one cell to the right.\n- Two cells down and one cell to the left.\n- Two cells to the right and one cell up.\n- Two cells to the right and one cell down.\n- Two cells to the left and one cell up.\n- Two cells to the left and one cell down.\n\nThe goal of the problem is to determine the probability that the knight remains on the chessboard after it has made exactly k moves or has moved off the chessboard.\n\nTo solve this problem, we can use dynamic programming. We can create a 3D DP array with dimensions (n x n x k+1). The DP array, denoted as dp[i][j][steps], represents the probability of the knight being at position (i, j) after making \'steps\' moves.\n\nThe base case for this DP problem is dp[i][j][0] = 1, meaning that the probability of the knight being at position (i, j) after 0 moves is 100%, as it hasn\'t moved yet.\n\nWe can then iterate through the number of steps, from 1 to k, and for each cell (i, j), calculate the probability of reaching that cell after \'steps\' moves. To calculate the probability at dp[i][j][steps], we sum up the probabilities from all eight possible moves that lead to cell (i, j) and update the DP array accordingly.\n\nAfter completing the DP computation, we can return the sum of all probabilities in the last step dp array that are still within the bounds of the chessboard (i.e., (0 \u2264 i < n) and (0 \u2264 j < n)).\n\nThe final returned value will be the probability that the knight remains on the board after it has stopped moving exactly k times.\n\n\n### try to reas the abouve part it will help you to understanding the problem !! \n\n\n\n\n\n# Apporach 1\n\n#### Dynamic Programming with Memoization:\n\n- To solve this problem efficiently, we will use dynamic programming with memoization. The memoization technique allows us to store and reuse already computed results, avoiding redundant calculations.\n- We\'ll create a 3D DP array (memo) to store the probabilities of the knight being at a specific cell (i, j) after \'steps\' moves.\n- The DP array will have dimensions of (n x n x k+1), where n is the size of the chessboard and k is the number of moves the knight makes.\n- We initialize the DP array with -1.0, indicating that the probability for that cell and move count is not yet computed.\n\n\n\n\n\n#### Base Case and Initialization:\n\n- The base case for the DP is when k is 0. In this case, the probability of the knight being at any cell (i, j) is 1 because the knight hasn\'t moved yet.\n- We initialize dp[i][j][0] = 1 for all valid (i, j) positions.\n\n\n\n#### Recursive Function:\n\n- We will create a recursive function (knightProbabilityDP) that calculates the probability of the knight being at a cell (i, j) after \'steps\' moves.\n- The function will take the current cell (row, col), chessboard size \'n\', and the remaining number of moves \'k\'.\n- Before performing any calculations, we will check if the cell (row, col) is out of bounds. If so, we return 0, indicating that the knight cannot be at that cell after \'steps\' moves.\n- If the probability for dp[row][col][k] is already computed (not equal to -1.0), we return the cached result.\n\n#### Recursive Calls:\n\n- In the recursive function, we use a loop to try all eight possible moves of the knight (two cells in a cardinal direction, then one cell in an orthogonal direction).\n- For each valid move, we recursively call the knightProbabilityDP function with the updated cell (newRow, newCol) and k - 1 (decrementing the number of moves).\n- We add up all the probabilities from the recursive calls, representing the probability of reaching cell (row, col) after \'steps\' moves.\n\n#### Updating DP and Returning Result:\n\n- Once we have computed the probability for dp[row][col][k], we store it in the DP array to reuse it later if needed.\n- The final result we want to calculate is the probability of the knight being on the board after k moves, starting from a given cell (startRow, startCol).\n- We call the recursive function (knightProbabilityDP) with the initial cell (startRow, startCol) and k, which will return the probability of the knight being at that cell after k moves.\n- We divide this probability by the total number of possible outcomes, which is 8^k (eight possible moves at each step), to get the final answer.\n\n### Output:\n\n- - The returned value is the probability that the knight remains on the board after it has stopped moving exactly k times, starting from the given cell (startRow, startCol). The value will be between 0 and 1.\n![upvote.jpg](https://assets.leetcode.com/users/images/3f575c98-90fb-4946-ab8f-2f550a47bc19_1689995372.261699.jpeg)\n\n## more optimsed code is given below !!\n\n# code \n```java []\npublic class Solution {\n    double[][][] dp;\n    int[] xmove = {-2, -2, -1, -1, 1, 1, 2, 2};\n    int[] ymove = {-1, 1, -2, 2, -2, 2, -1, 1};\n\n    public double knightProbability(int n, int k, int row, int col) {\n        dp = new double[n][n][k + 1];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                Arrays.fill(dp[i][j], -1.0);\n            }\n        }\n        double favourableOutcome = solve(row, col, n, k);\n        double totalOutcome = Math.pow(8, k);\n        return favourableOutcome / totalOutcome;\n    }\n\n    private double solve(int row, int col, int n, int k) {\n        if (row < 0 || col < 0 || row >= n || col >= n) return 0;\n        if (k == 0) return 1;\n        if (dp[row][col][k] != -1.0) return dp[row][col][k];\n\n        double ans = 0;\n\n        for (int i = 0; i < 8; i++) {\n            ans += solve(row + xmove[i], col + ymove[i], n, k - 1);\n        }\n\n        return dp[row][col][k] = ans;\n    }\n}\n```\n```c++ []\nclass Solution {\npublic:\ndouble dp[26][26][102];\n    int xmove[8] = {-2,-2,-1,-1,1,1,2,2};\n    int ymove[8] = {-1,1,-2,2,-2,2,-1,1};\n  double solve(int row,int col,int n,int k){\n        if(row < 0 || col < 0 || row >= n || col >= n) return 0;\n        if(k == 0) return 1;\n        if(dp[row][col][k] != -1.0) return dp[row][col][k];\n        \n       double ans = 0;\n        \n        for(int i=0;i<8;i++){\n            ans += solve(row+xmove[i], col+ymove[i], n, k-1);\n        }\n        \n        return dp[row][col][k] = ans;\n    }\n    double knightProbability(int n, int k, int row, int col) {\n        for(int i=0;i<26;i++){\n            for(int j=0;j<26;j++){\n                for(int k=0;k<102;k++){\n                    dp[i][j][k]=-1;\n                }\n            }\n        }\n        double favourableoutcome = solve(row,col,n,k);\n        double totaloutcome = pow(8,k);\n        return favourableoutcome/totaloutcome;\n    }\n};\n```\n\n\nthe running time of the code below !! \n![Screenshot 2023-07-22 084626.png](https://assets.leetcode.com/users/images/309de975-6318-4612-933a-997caa21dc26_1689995935.9950595.png)\n\n\n# the more optimised \n#### java : \n```\nclass Solution {\n    private final int[][] moves = {{2, 1}, {-2, 1}, {1, 2}, {-1, 2}, {2, -1}, {-2, -1}, {1, -2}, {-1, -2}};\n\n    public double knightProbability(int n, int k, int row, int column) {\n        double[][][] cache = new double[n / 2 + 1][n / 2 + 1][k + 1];\n        return solver(n, k, row, column, cache);\n    }\n    private double solver(int n, int k, int row, int column, double[][][] memo) {\n        if (row < 0 || row >= n || column < 0 || column >= n) return 0.0;\n        if (k == 0) return 1.0;\n\n        row = Math.min(row, n - 1 - row);\n        column = Math.min(column, n - 1 - column);\n\n        if (row < column) return solver(n, k, column, row, memo);\n        if (memo[row][column][k] != 0.0) return memo[row][column][k];\n\n        double probability = 0.0;\n        for (int[] move : moves) {\n            probability += solver(n, k - 1, row + move[0], column + move[1], memo) / 8.0;\n        }\n        memo[row][column][k] = probability;\n        return probability;\n    }\n}\n\n```\n# Aproach -2 \n#### Representation of Moves:\n\n-Instead of representing the knight\'s moves using two separate arrays (xMoves and yMoves), the solution directly uses the relative positions for all eight possible moves in the \'moves\' array.\n-Each entry in the \'moves\' array represents the relative change in row and column that the knight makes for a particular move.\n\n#### Cache and Optimized Search Space:\n\n- The solution uses a 3D cache array \'memo\' with dimensions [n/2 + 1][n/2 + 1][k+1]. The purpose of this cache is to store previously computed probabilities to avoid redundant calculations.\n- Additionally, the solution makes use of symmetry in the chessboard. Since the board is symmetrical with respect to the center, it\'s more efficient to compute probabilities in the top-right quadrant of the chessboard only and then use this symmetry to fill in the other quadrants.\n\n#### Row and Column Bounds Adjustment:\n\n- Before starting the recursive calls, the solution adjusts the row and column values based on their distance from the center of the board (n/2). This adjustment helps reduce the search space by considering only the top-right quadrant of the chessboard.\n\n#### Recursive Function:\n\n- The recursive function (solver) takes in the current position (row, column), chessboard size \'n\', the remaining number of moves \'k\', and the memoization cache.\n- The base case checks if the knight is out of bounds or has made all the moves (k == 0). If so, it returns the corresponding probability (0.0 or 1.0).\n- The function calculates the probability of reaching the current cell after \'k\' moves by recursively trying all eight possible moves.\n- Instead of dividing the result by 8.0 in each recursive call, it accumulates the probabilities and divides the final result once before storing it in the cache.\n\n#### Using Memoization:\n\n- The function checks if the probability for the current cell and move count is already present in the cache (memo). If so, it returns the cached result, avoiding redundant computations.\n\n### Output:\n\nThe main function initializes the cache, and then calls the recursive function (solver) with the initial cell (row, column) and k.\nThe returned value is the probability that the knight remains on the board after it has stopped moving exactly k times, starting from the given cell (row, column). The value will be between 0 and 1.
['Java']