🙌 Easy to Understand | DP | With Explanation 📖
Intuition\n\n- The code uses dynamic programming to solve the knight probability problem. The probability array is initialized to all zeros, and then the probab
# Intuition\n\n- The code uses dynamic programming to solve the knight probability problem. The probability array is initialized to all zeros, and then the probability of the knight being on the board after each move is calculated. The base case is that the knight is already on the board, so the probability is 1. The recursive step is to iterate over all possible moves and update the probability of the knight being on the board after each move. The final probability is the probability that the knight is on the board after k moves.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- The code below uses the DP approach. This approach is more efficient than recursion because it stores the probabilities for moves that have already been made. \na step-by-step approach for the optimized code to find the probability that the knight remains on the board after making exactly k moves:\n\n1. Initialize a 2D dp array of size n x n to store the probabilities of the knight being on the board from a specific cell.\n2. Set the initial probability of the starting cell (row, column) to 1.0, as the knight starts from this cell.\n3. For each move from 1 to k, do the following:\na. Create a new 2D newDp array to store the updated probabilities after one move.\nb. Iterate through each cell (r, c) in the original dp array:\n    - For each possible move of the knight, calculate the new position (nr, nc) after the move.\n    - If the new position (nr, nc) is within the bounds of the n x n chessboard, update the probability in newDp[r][c] by adding the probability from the original dp[nr][nc] / 8.0. This is because the knight moves uniformly at random, so each move has a probability of 1/8 to be chosen.\n    - Set dp to newDp to keep the updated probabilities for the next iteration.\n4. After completing all k moves, calculate the total probability of the knight remaining on the board by summing up all the probabilities from the final dp array.\n5. Return the total probability as the result.\n\n- The isValid helper function is used to check whether a move is valid, i.e., whether the new position (r, c) after the move is within the bounds of the n x n chessboard. This function returns true if the move is valid, and false otherwise.\n\n# Complexity\n- Time complexity: O(n^2 * k). \nThis is because the outer loop iterates over all possible values of k, and the inner loop iterates over all possible rows and columns.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Java []\nclass Solution {\n    private final int[][] moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};\n\n    public double knightProbability(int n, int k, int row, int column) {\n        double[][] dp = new double[n][n];\n        dp[row][column] = 1.0;\n\n        for(int move = 1; move<=k; move++) {\n            double[][] ndp = new double[n][n];\n            for(int r = 0; r<n; r++) {\n                for(int c = 0; c<n; c++) {\n                    for(int[] m: moves) {\n                        int nr = r+m[0];\n                        int nc = c+m[1];\n                        if (isValid(nr, nc, n)) ndp[r][c] += dp[nr][nc]/8.0;\n                    }\n                }\n            }\n            dp = ndp;\n        }\n\n        double prob = 0.0;\n        for (int r = 0; r < n; r++) {\n            for (int c = 0; c < n; c++) {\n                prob += dp[r][c];\n            }\n        }\n\n        return prob;\n    }\n\n    private boolean isValid(int r, int c, int n) {\n        return r >= 0 && r < n && c >= 0 && c < n;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    double knightProbability(int n, int k, int row, int column) {\n        vector<vector<double>> dp(n, vector<double>(n, 0));\n        dp[row][column] = 1;\n\n        vector<vector<int>> moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};\n\n        for (int move = 1; move <= k; move++) {\n            vector<vector<double>> newDp(n, vector<double>(n, 0));\n            for (int r = 0; r < n; r++) {\n                for (int c = 0; c < n; c++) {\n                    for (const auto& m : moves) {\n                        int newR = r + m[0];\n                        int newC = c + m[1];\n                        if (isValid(newR, newC, n)) {\n                            newDp[r][c] += dp[newR][newC] / 8.0;\n                        }\n                    }\n                }\n            }\n            dp = newDp;\n        }\n\n        double probability = 0;\n        for (int r = 0; r < n; r++) {\n            for (int c = 0; c < n; c++) {\n                probability += dp[r][c];\n            }\n        }\n\n        return probability;\n    }\n\n    bool isValid(int r, int c, int n) {\n        return r >= 0 && r < n && c >= 0 && c < n;\n    }\n};\n```\n```Python3 []\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        dp = [[0] * n for _ in range(n)]\n        dp[row][column] = 1\n\n        moves = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]\n\n        for move in range(1, k + 1):\n            new_dp = [[0] * n for _ in range(n)]\n            for r in range(n):\n                for c in range(n):\n                    for m in moves:\n                        new_r = r + m[0]\n                        new_c = c + m[1]\n                        if 0 <= new_r < n and 0 <= new_c < n:\n                            new_dp[r][c] += dp[new_r][new_c] / 8.0\n            dp = new_dp\n\n        probability = 0.0\n        for r in range(n):\n            for c in range(n):\n                probability += dp[r][c]\n\n        return probability\n```\n```C []\ndouble knightProbability(int n, int k, int row, int column) {\n    double dp[n][n];\n    memset(dp, 0, sizeof(dp));\n    dp[row][column] = 1;\n\n    int moves[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};\n\n    for (int move = 1; move <= k; move++) {\n        double newDp[n][n];\n        memset(newDp, 0, sizeof(newDp));\n        for (int r = 0; r < n; r++) {\n            for (int c = 0; c < n; c++) {\n                for (int i = 0; i < 8; i++) {\n                    int newR = r + moves[i][0];\n                    int newC = c + moves[i][1];\n                    if (newR >= 0 && newR < n && newC >= 0 && newC < n) {\n                        newDp[r][c] += dp[newR][newC] / 8.0;\n                    }\n                }\n            }\n        }\n        memcpy(dp, newDp, sizeof(dp));\n    }\n\n    double probability = 0;\n    for (int r = 0; r < n; r++) {\n        for (int c = 0; c < n; c++) {\n            probability += dp[r][c];\n        }\n    }\n\n    return probability;\n}\n```\n\n> If you find my solution helpful, I would greatly appreciate your one upvote.
['Dynamic Programming', 'C', 'C++', 'Java', 'Python3']