C# Solution for Knight Probability in Chess Board Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be solved using dynamic programming. We need to find the probability th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be solved using dynamic programming. We need to find the probability that the knight remains on the board after exactly k moves starting from the given position. To do this, we can calculate the probabilities for all possible cells on the board after each move and keep updating the probabilities based on the previous positions.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Create a 3D array dp[n][n][k+1] to store the probabilities. dp[i][j][s] represents the probability of the knight being on cell (i,j) after s moves.\n- Initialize the base case: dp[row][column][0] = 1, since the knight hasn\'t moved yet.\n- Use a directions array to store all possible knight moves (8 in total).\n- For each s from 1 to k, and each cell (i,j) on the board:\n1. Calculate the probability of reaching cell (i,j) after s moves by summing up the probabilities from all possible previous positions in the last move.\n1. Update dp[i][j][s] by dividing the sum by 8 (since there are 8 possible moves for the knight).\n- Finally, sum up the probabilities for all cells on the board after k moves to get the total probability that the knight remains on the board.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this solution is O(n^2 * k), where n is the size of the chessboard and k is the number of moves. The nested loops iterate over all cells on the board and for each cell, the algorithm performs a constant number of operations.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(n^2 * k) as well, due to the 3D dp array used to store the probabilities for each cell and each move.\n\n# Code\n```\npublic class Solution {\n    public double KnightProbability(int n, int k, int row, int column) {\n        int[][] directions = new int[][] {\n        new int[] { 2, 1 },\n        new int[] { 1, 2 },\n        new int[] { -1, 2 },\n        new int[] { -2, 1 },\n        new int[] { -2, -1 },\n        new int[] { -1, -2 },\n        new int[] { 1, -2 },\n        new int[] { 2, -1 }\n    };\n    \n    double[,,] dp = new double[n, n, k + 1];\n    dp[row, column, 0] = 1;\n    \n    for (int s = 1; s <= k; s++) {\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                foreach (var dir in directions) {\n                    int prevRow = i + dir[0];\n                    int prevCol = j + dir[1];\n                    \n                    if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {\n                        dp[i, j, s] += dp[prevRow, prevCol, s - 1] / 8;\n                    }\n                }\n            }\n        }\n    }\n    \n    double totalProbability = 0;\n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < n; j++) {\n            totalProbability += dp[i, j, k];\n        }\n    }\n    \n    return totalProbability;\n    }\n}\n```
['C#']