Very Easy to understand +Video || C++ || Java || Python
Intuition\n Describe your first thoughts on how to solve this problem. \njust do dfs and after dfs count all the cells that are visited after k move then \njust
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\njust do dfs and after dfs count all the cells that are visited after k move then \njust calculate by formula p=favorableoutcome/totaloutcome.Dfs and memoize also so that we are not solving problems that are already solved.this will reduce time complexity.\n\nFor detailed explanation you can refer to my youtube channel (hindi Language)\nhttps://youtu.be/abaZ13EXgxQ\n or link in my profile.Here,you can find any solution in playlists monthwise from june 2023 with detailed explanation.i upload daily leetcode solution video with short and precise explanation (5-10) minutes.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. The solution defines a class named "Solution" with a public function "knightProbability" that takes four parameters: n (size of the chessboard), k (number of moves), row (starting row index), and col (starting column index).\n\n2. The class contains a 3D array "dp" to store the results of subproblems. dp[i][j][k] will store the probability of the knight remaining on the board after making k moves starting from position (i, j).\n\n3. Two integer arrays, "xmove" and "ymove," are used to represent all possible moves a knight can make on the chessboard.\n\n4. The "solve" function is a recursive function that calculates the probability of the knight remaining on the board after k moves starting from position (row, col).\n\n5. The base cases for the recursive function are:\n   - If the knight moves outside the board (row < 0, col < 0, row >= n, col >= n), the probability is 0.\n   - If the number of moves (k) becomes 0, the probability is 1 (since the knight remains on the board after 0 moves).\n\n6. The function first checks if the result for the current state (row, col, k) is already calculated and stored in the "dp" array. If so, it returns the precalculated value to avoid redundant calculations.\n\n7. If the result for the current state is not available, the function computes it using a loop that iterates over all possible knight moves. For each move, it recursively calls the "solve" function to get the probability of the knight remaining on the board after making k-1 moves from the new position (row+xmove[i], col+ymove[i]). The result is then accumulated in the "ans" variable.\n\n8. The probability for the current state (row, col, k) is stored in the "dp" array to avoid recomputation in future calls with the same parameters.\n\n9. In the "knightProbability" function, the "dp" array is initialized with -1.0 for all positions and moves using a nested loop.\n\n10. The function then calls the "solve" function to calculate the probability of the knight remaining on the board after k moves starting from the given position (row, col).\n\n11. The final result is the favorable outcome (the probability of the knight remaining on the board) divided by the total number of possible outcomes (8^k), which is the total number of valid knight moves in k steps.\n\n12. The function returns the computed probability.\n\n\n\n# Complexity\n- Time complexity:$$O(n*n*k)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n*n*k)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\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```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```\n```Python []\nclass Solution:\n    def __init__(self):\n        self.dp = None\n        self.xmove = [-2, -2, -1, -1, 1, 1, 2, 2]\n        self.ymove = [-1, 1, -2, 2, -2, 2, -1, 1]\n\n    def knightProbability(self, n: int, k: int, row: int, col: int) -> float:\n        self.dp = [[[-1.0 for _ in range(k + 1)] for _ in range(n)] for _ in range(n)]\n        favourableOutcome = self.solve(row, col, n, k)\n        totalOutcome = 8 ** k\n        return favourableOutcome / totalOutcome\n\n    def solve(self, row: int, col: int, n: int, k: int) -> float:\n        if row < 0 or col < 0 or row >= n or col >= n:\n            return 0\n        if k == 0:\n            return 1\n        if self.dp[row][col][k] != -1.0:\n            return self.dp[row][col][k]\n\n        ans = 0\n        for i in range(8):\n            ans += self.solve(row + self.xmove[i], col + self.ymove[i], n, k - 1)\n\n        self.dp[row][col][k] = ans\n        return ans\n\n```\n
['Dynamic Programming', 'Depth-First Search', 'Python', 'C++', 'Java']