Ex-Amazon explains a solution with a video, Python, JavaScript and Java
Intuition\nCreating two boards and keep current and next probability.\nThis Python solution beats 92%.\n\n\n\n---\n\n# Solution Video\n## *** Please upvote for 
# Intuition\nCreating two boards and keep current and next probability.\nThis Python solution beats 92%.\n\n![\u30B9\u30AF\u30EA\u30FC\u30F3\u30B7\u30E7\u30C3\u30C8 2023-07-22 15.45.14.png](https://assets.leetcode.com/users/images/417526bc-b03e-4750-847a-0f2b72389d9b_1690008499.6700006.png)\n\n---\n\n# Solution Video\n## *** Please upvote for this article. *** \n\nhttps://youtu.be/e3oSatmeAPo\n\n# Subscribe to my channel from here. I have 227 videos as of July 22th\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n---\n\n# Approach\nThis is based on Python. Other language might be different a bit.\n\n1. Define a list `moves` that contains all possible directions a knight can move to. Each element in `moves` is a tuple representing the relative coordinates for each direction.\n\n2. Create two 2D lists `cur_board` and `next_board`, both of size `n x n`, and initialize all elements to 0.0.\n\n3. Set the starting position `next_board[row][column]` to 1.0, as the knight is initially at this cell.\n\n4. Iterate `k` times, where `k` represents the number of moves the knight can take.\n\n5. For each iteration, update `cur_board` with the values from `next_board`, and reset `next_board` to a new 2D list of size `n x n` filled with zeros.\n\n6. For each cell `(r, c)` in the `cur_board` (representing the current state of the knight at each position), calculate the probability of reaching the neighboring cells by taking all possible moves (as specified in `moves`).\n\n7. If the current cell is not reachable (`cur_board[r][c] == 0.0`), continue to the next cell.\n\n8. If the neighboring cell `(next_row, next_col)` is within the chessboard (0 <= next_row < n and 0 <= next_col < n), update the probability of reaching that cell in `next_board` by adding the probability from the current cell divided by 8.0. This is because there are 8 possible moves the knight can take from the current cell.\n\n9. Repeat steps 6-8 for all cells in the `cur_board`, updating the `next_board` with the new probabilities.\n\n10. After `k` iterations, the `next_board` will contain the probabilities of the knight being at each cell on the chessboard after `k` moves.\n\n11. Calculate the total probability of the knight being on the chessboard by summing up all the probabilities in `next_board`.\n\n12. Return the total probability as the final result.\n\nThe code uses dynamic programming to calculate the probabilities efficiently and stores the intermediate results in `cur_board` and `next_board` for each iteration to avoid redundant calculations.\n\n# Complexity\nThis is based on Python. Other language might be different a bit.\n\n- Time complexity: O(k * n^2)\nThe outer loop runs k times, and the two nested loops run n^2 times each\n\n- Space complexity: O(n^2)\nTwo 2D arrays, cur_board and next_board, are created with dimensions n x n, each occupying n^2 space.\n\nk represents the number of moves the knight can take, and n is the size of the chessboard. \n\n```python []\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]\n\n        cur_board = [[0.0] * n for _ in range(n)]\n        next_board = [[0.0] * n for _ in range(n)]\n        next_board[row][column] = 1.0\n\n        for _ in range(k):\n            cur_board, next_board = next_board, [[0.0] * n for _ in range(n)]\n\n            for r in range(n):\n                for c in range(n):\n                    if cur_board[r][c] == 0.0:\n                        continue\n                    \n                    for dr, dc in moves:\n                        next_row, next_col = r + dr, c + dc\n\n                        if 0 <= next_row < n and 0 <= next_col < n:\n                            next_board[next_row][next_col] += cur_board[r][c] / 8.0\n        \n        total = 0.0\n        for r in range(n):\n            for c in range(n):\n                total += next_board[r][c]\n        \n        return total\n```\n``` javascript []\n/**\n * @param {number} n\n * @param {number} k\n * @param {number} row\n * @param {number} column\n * @return {number}\n */\nvar knightProbability = function(n, k, row, column) {\n    const moves = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]];\n\n    let curBoard = Array.from({ length: n }, () => Array(n).fill(0.0));\n    let nextBoard = Array.from({ length: n }, () => Array(n).fill(0.0));\n    nextBoard[row][column] = 1.0;\n\n    for (let i = 0; i < k; i++) {\n        [curBoard, nextBoard] = [nextBoard, Array.from({ length: n }, () => Array(n).fill(0.0))];\n\n        for (let r = 0; r < n; r++) {\n            for (let c = 0; c < n; c++) {\n                if (curBoard[r][c] === 0.0) {\n                    continue;\n                }\n\n                for (const [dr, dc] of moves) {\n                    const nextRow = r + dr;\n                    const nextCol = c + dc;\n\n                    if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {\n                        nextBoard[nextRow][nextCol] += curBoard[r][c] / 8.0;\n                    }\n                }\n            }\n        }\n    }\n\n    let total = 0.0;\n    for (let r = 0; r < n; r++) {\n        for (let c = 0; c < n; c++) {\n            total += nextBoard[r][c];\n        }\n    }\n\n    return total;    \n};\n```\n```java []\nclass Solution {\n\n    public double knightProbability(int n, int k, int row, int column) {\n        int[][] moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};\n\n        double [][] curBoard;\n        double [][] nextBoard = new double[n][n];\n        nextBoard[row][column] = 1.0;\n        \n        for (int i = 0; i < k; i++) {\n            curBoard = nextBoard;\n            nextBoard = new double[n][n];\n            \n            for (int r = 0; r < n; r++) {\n                for (int c = 0; c < n; c++) {\n                    if (curBoard[r][c] == 0.0)\n                        continue;\n                    \n                    for (int [] dir : moves) {\n                        int nextRow = r + dir[0];\n                        int nextCol = c + dir[1];\n                        \n                        if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {\n                            nextBoard[nextRow][nextCol] += curBoard[r][c] / 8.0;\n                        }\n                    }\n                }\n            }\n        }\n        \n        double total = 0.0;\n        for (int r = 0; r < n; r++)\n            for (int c = 0; c < n; c++)\n                total += nextBoard[r][c];\n        \n        return total;\n    }\n}\n```\n
['Java', 'Python3', 'JavaScript']