Easy-Soln👁️ | Well-Explained✅ | Adobe🔥
If you found my answer helpful, please consider giving it an upvote\uD83D\uDE0A\n#ReviseWithArsh #6Companies30Days Challenge 2023\nChallenge Company 3 : Adobe\n
## If you found my answer helpful, please consider giving it an upvote\uD83D\uDE0A\n***#ReviseWithArsh #6Companies30Days Challenge 2023\nChallenge Company 3 : Adobe\nQ6. Knight in a Chessboard***\n\n### Complexity\n- Time complexity: O(n^2*k)\n- Space complexity: O(n^2k)\n\n### Code\n```\nclass Solution {\npublic:\n    double knightProbability(int chessBoardSize, int moves, int currentRow, int currentCol){\n        // Initialize 3D dp array to store the probability of knight being on a certain square after k moves\n        vector<vector<vector<double>>> dp(moves + 1, vector<vector<double>> (chessBoardSize, vector<double>(chessBoardSize, -1)));\n            // Call the helper function to solve the problem\n    return solve(chessBoardSize, moves, currentRow, currentCol, dp);\n}\nprivate:\n    double solve(int chessBoardSize, int moves, int currentRow, int currentCol, vector<vector<vector<double>>>& dp){\n    // If the knight is out of the chess board, return 0\n    if (currentRow < 0 || currentRow >= chessBoardSize || currentCol < 0 || currentCol >= chessBoardSize) return 0;\n    // If the knight has made k moves, return 1 as it will be on the chess board\n    if (moves == 0) return 1;\n        // If the probability for this state is already calculated, return it\n    if (dp[moves][currentRow][currentCol] != -1)\n        return dp[moves][currentRow][currentCol];\n    \n    // Total probability is the sum of probabilities of all 8 possible moves from the current square\n    double total = solve(chessBoardSize, moves - 1, currentRow - 2, currentCol + 1, dp) + solve(chessBoardSize, moves - 1, currentRow - 1, currentCol + 2, dp)\n                + solve(chessBoardSize, moves - 1, currentRow + 1, currentCol + 2, dp) + solve(chessBoardSize, moves - 1, currentRow + 2, currentCol + 1, dp)\n                + solve(chessBoardSize, moves - 1, currentRow + 2, currentCol - 1, dp) + solve(chessBoardSize, moves - 1, currentRow + 1, currentCol - 2, dp)\n                + solve(chessBoardSize, moves - 1, currentRow - 1, currentCol - 2, dp) + solve(chessBoardSize, moves - 1, currentRow - 2, currentCol - 1, dp);\n        \n    total = total / 8;\n    return dp[moves][currentRow][currentCol] = total;\n    }\n};\n\n\n```
['C++']