🔥 [VIDEO] Conquer The Chess Knight Challenge with Python and Dynamic Programming!
Intuition\nWhen first approaching this problem, I thought of the knight\'s eight possible moves on a chessboard and how some of these moves can cause it to fall
# Intuition\nWhen first approaching this problem, I thought of the knight\'s eight possible moves on a chessboard and how some of these moves can cause it to fall off the board. I recognized the probability aspect of the problem and the fact that each move the knight makes is independent of the others. This made me think about using dynamic programming to solve this problem as it involves computing the probabilities of independent events and has overlapping sub-problems, which are characteristics that dynamic programming excels at.\n\nhttps://youtu.be/tp5UqIarBGQ\n\n# Approach\nI used a dynamic programming approach to solve this problem. The idea is to use a 3D array to keep track of the probability of the knight being on each cell after a certain number of moves. The dp[i][j][k] cell in this array represents the probability of the knight being in cell (j, k) after i moves. For each cell, I calculate its probability by averaging the probabilities of the knight reaching that cell from each of its possible previous positions. The base case is that the knight is on the board (with a probability of 1) if it starts on the board. Finally, I sum up the probabilities in all cells after k moves to get the total probability of the knight remaining on the board.\n\n# Complexity\n- Time complexity: The time complexity of this solution is $$O(n^2 * k)$$ where n is the size of the board and k is the number of moves. This is because for each move, I iterate over all cells in the n by n board, and for each cell, I calculate its probability based on the probabilities of its previous positions.\n  \n- Space complexity: The space complexity of this solution is $$O(n^2 * k)$$ due to the 3D dp array used to store the probabilities of the knight being on each cell after a certain number of moves.\n\n# Code\n``` Python []\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        moves = [(1, 2), (2, 1), (-1, 2), (2, -1), (-1, -2), (-2, -1), (1, -2), (-2, 1)] \n        dp = [[0 for _ in range(n)] for _ in range(n)]\n        dp_prev = [[0 for _ in range(n)] for _ in range(n)]\n        dp_prev[row][column] = 1\n\n        for step in range(k):\n            for r in range(n):\n                for c in range(n):\n                    dp[r][c] = 0\n                    for dr, dc in moves:\n                        prev_r, prev_c = r - dr, c - dc\n                        if 0 <= prev_r < n and 0 <= prev_c < n:\n                            dp[r][c] += dp_prev[prev_r][prev_c] / 8.0\n            dp, dp_prev = dp_prev, dp \n\n        total_probability = sum(sum(dp_prev[r][c] for c in range(n)) for r in range(n))\n        return total_probability\n```\n``` JavaScript []\nvar knightProbability = function(n, k, r, c) {\n    const moves = [[1,2], [2,1], [-1,2], [2,-1], [-1,-2], [-2,-1], [1,-2], [-2,1]];\n    let dp = Array.from({length: n}, () => new Array(n).fill(0));\n    let dpPrev = Array.from({length: n}, () => new Array(n).fill(0));\n    dpPrev[r][c] = 1;\n\n    for(let step = 0; step < k; step++) {\n        for(let i = 0; i < n; i++) {\n            for(let j = 0; j < n; j++) {\n                dp[i][j] = 0;\n                for(let [dr, dc] of moves) {\n                    let prevR = i - dr;\n                    let prevC = j - dc;\n                    if(prevR >= 0 && prevR < n && prevC >= 0 && prevC < n) {\n                        dp[i][j] += dpPrev[prevR][prevC] / 8.0;\n                    }\n                }\n            }\n        }\n        [dp, dpPrev] = [dpPrev, dp];\n    }\n\n    let totalProbability = 0;\n    for(let i = 0; i < n; i++) {\n        for(let j = 0; j < n; j++) {\n            totalProbability += dpPrev[i][j];\n        }\n    }\n\n    return totalProbability;\n};\n```\n``` C++ []\nclass Solution {\npublic:\n    double knightProbability(int n, int k, int row, int column) {\n        vector<vector<int>> moves = {{1, 2}, {2, 1}, {-1, 2}, {2, -1}, {-1, -2}, {-2, -1}, {1, -2}, {-2, 1}};\n        vector<vector<double>> dp(n, vector<double>(n, 0));\n        vector<vector<double>> dpPrev(n, vector<double>(n, 0));\n        dpPrev[row][column] = 1;\n        \n        for (int step = 0; step < k; step++) {\n            for (int i = 0; i < n; i++) {\n                for (int j = 0; j < n; j++) {\n                    dp[i][j] = 0;\n                    for (auto& move : moves) {\n                        int prevR = i - move[0];\n                        int prevC = j - move[1];\n                        if (prevR >= 0 && prevR < n && prevC >= 0 && prevC < n) {\n                            dp[i][j] += dpPrev[prevR][prevC] / 8.0;\n                        }\n                    }\n                }\n            }\n            swap(dp, dpPrev);\n        }\n        \n        double totalProbability = 0;\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                totalProbability += dpPrev[i][j];\n            }\n        }\n        \n        return totalProbability;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public double knightProbability(int n, int k, int r, int c) {\n        int[][] moves = {{1, 2}, {2, 1}, {-1, 2}, {2, -1}, {-1, -2}, {-2, -1}, {1, -2}, {-2, 1}};\n        double[][] dp = new double[n][n];\n        double[][] dpPrev = new double[n][n];\n        dpPrev[r][c] = 1;\n        \n        for (int step = 0; step < k; step++) {\n            for (int i = 0; i < n; i++) {\n                for (int j = 0; j < n; j++) {\n                    dp[i][j] = 0;\n                    for (int[] move : moves) {\n                        int prevR = i - move[0];\n                        int prevC = j - move[1];\n                        if (prevR >= 0 && prevR < n && prevC >= 0 && prevC < n) {\n                            dp[i][j] += dpPrev[prevR][prevC] / 8.0;\n                        }\n                    }\n                }\n            }\n            double[][] temp = dp;\n            dp = dpPrev;\n            dpPrev = temp;\n        }\n        \n        double totalProbability = 0;\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                totalProbability += dpPrev[i][j];\n            }\n        }\n        \n        return totalProbability;\n    }\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn knight_probability(n: i32, k: i32, r: i32, c: i32) -> f64 {\n        let moves = [(1, 2), (2, 1), (-1, 2), (2, -1), (-1, -2), (-2, -1), (1, -2), (-2, 1)];\n        let mut dp = vec![vec![0.0; n as usize]; n as usize];\n        let mut dp_prev = vec![vec![0.0; n as usize]; n as usize];\n        dp_prev[r as usize][c as usize] = 1.0;\n\n        for _step in 0..k {\n            for i in 0..n {\n                for j in 0..n {\n                    dp[i as usize][j as usize] = 0.0;\n                    for &(dr, dc) in &moves {\n                        let prev_r = i - dr;\n                        let prev_c = j - dc;\n                        if prev_r >= 0 && prev_r < n && prev_c >= 0 && prev_c < n {\n                            dp[i as usize][j as usize] += dp_prev[prev_r as usize][prev_c as usize] / 8.0;\n                        }\n                    }\n                }\n            }\n            std::mem::swap(&mut dp, &mut dp_prev);\n        }\n\n        let mut total_probability = 0.0;\n        for i in 0..n {\n            for j in 0..n {\n                total_probability += dp_prev[i as usize][j as usize];\n            }\n        }\n        total_probability\n    }\n}\n```
['C++', 'Java', 'Python3', 'Rust', 'JavaScript']