Solution for Knight Probability in Chessboard leetcode problem 688.
Intuition\n Describe your first thoughts on how to solve this problem. \nThe code is implementing a solution to the "Knights Probability in Chessboard" problem 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe code is implementing a solution to the "Knights Probability in Chessboard" problem using dynamic programming. The goal is to calculate the probability that a knight starting at a given position (row, column) on an n x n chessboard will remain on the board after exactly k moves.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe code initializes a 2D array curr of size n x n to store the current probabilities of the knight being at each cell after making m moves (initially set to 0 for all cells).\nIt sets the probability of the knight being at the starting position (row, column) to 1 in the curr array, as the knight starts there.\nThen, it initializes another 2D array next of size n x n to store the updated probabilities after each move.\nFor each move from 1 to k, the code iterates through the curr array, and for each cell with a non-zero probability, it calculates the probabilities for all possible moves the knight can make. It updates the next array accordingly.\nAfter completing all k moves, the final probabilities of the knight being at each cell are stored in the curr array.\nFinally, the code calculates the sum of probabilities of the knight being at all cells in the curr array and returns the total probability.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of the given solution is O(n^2 * k). It involves a triple nested loop, where the outer loop runs k times (for each move), and the inner two loops iterate through the n x n chessboard. The innermost loop involves checking the validity of the knight\'s possible moves, which takes constant time.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nThe space complexity of the given solution is O(n^2). It uses two 2D arrays curr and next, each of size n x n, to store the probabilities of the knight being at each cell. Additionally, there\'s a constant-sized 2D array dir used to represent the possible moves of the knight. The space used by these arrays does not depend on the value of k. Hence, the overall space complexity is determined by the size of the chessboard, which is n x n.\n- Space complexity:\n\n# Code\n```\nclass Solution {\n    int[][] dir = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};\n    public boolean isValid(int i, int j, int n){\n    if(i>=0 && j>=0 && i<n && j<n){\n        return true;\n    }\n    return false;\n    }\n    public double knightProbability(int n, int k, int row, int column) {\n        double[][] curr = new double[n][n];\n        curr[row][column] = 1;\n        double[][] next = new double[n][n];\n        for(int m = 1; m<=k; m++){\n            for(int i = 0; i<n; i++){\n                for(int j = 0; j<n; j++){\n                    if(curr[i][j]!=0){\n                        for(int[] d : dir){\n                            int ni = i + d[0];\n                            int nj = j + d[1];\n                            if(isValid(ni,nj,n)){\n                                next[ni][nj] += curr[i][j]/8.0;\n                            }\n                        }\n                    }\n                }\n            }\n            curr = next;\n            next = new double[n][n];\n        }\n        \n        double sum = 0.0; \n        for(int i = 0; i<n ;i++){\n            for(int j = 0; j<n; j++){\n                    sum += curr[i][j];\n            }\n        }\n        return sum;\n    }\n}\n```\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/3fc44a76-dad9-4d65-9a7b-5ede60ed2595_1690036878.9690084.jpeg)\n
['Java']