🔥🔥 Variety of Solutions 🔥🔥 || Space Optimized at end || C++||
The 2D vector dp is used to store the probability of the knight being at each cell after m moves, where m is from 0 to k. Initially, dp[row][col] is set to 1.0,
The 2D vector dp is used to store the probability of the knight being at each cell after m moves, where m is from 0 to k. Initially, dp[row][col] is set to 1.0, as the knight starts at this cell with a probability of 1.\n\nWe then loop from m = 1 to k. In each iteration, we create a new 2D vector new_dp, which will be used to store the updated probabilities for m moves. We calculate the probabilities for each cell (x, y) based on the probabilities from the previous iteration.\n\nFor each cell (x, y) in the chessboard, we check all eight possible moves of the knight (using the dx and dy arrays). If the next move (nx, ny) is within the bounds of the chessboard (i.e., 0 <= nx < n and 0 <= ny < n), we update the probability in new_dp[nx][ny] by adding dp[x][y] / 8.0. This is because each move has an equal probability of occurring, and there are 8 possible moves in total.\n\nAfter updating all the probabilities for m moves, we assign dp to new_dp using dp = move(new_dp). This effectively updates the probabilities for m moves in the original dp vector, and we can proceed to the next iteration.\n\nOnce we finish all iterations from m = 1 to k, we have the final probabilities of the knight being at each cell after making k moves.\n\nFinally, we calculate the sum of all probabilities in dp, which represents the total probability that the knight remains on the board after making exactly k moves. This value is stored in the variable ans, which is returned as the result.\n\n# Code\n```\n// class Solution {\n// public:\n//     int dy[8] = {1, -1, 2, -2, 1, -1, 2, -2};\n//     int dx[8] = {2, 2, 1, 1, -2, -2, -1, -1};\n\n//     bool isValid(int x, int y, int n) {\n//         if (x >= 0 && x < n && y >= 0 && y < n) {\n//             return true;\n//         }\n//         return false;\n//     }\n\n//     double memo[26][101][101]; // Adjust size based on the given constraints\n\n//     double solve(int n, int k, int x, int y, double prob) {\n//         if (k == 0) {\n//             return 1;\n//         }\n\n//         if (memo[n][x][y] != 0) {\n//             return memo[n][x][y];\n//         }\n\n//         double res = 0;\n//         for (int i = 0; i < 8; i++) {\n//             int nx = x + dx[i];\n//             int ny = y + dy[i];\n\n//             if (isValid(nx, ny, n)) {\n//                 res += (solve(n, k - 1, nx, ny, prob / 8.0)) / 8.0;\n//             }\n//         }\n\n//         memo[n][x][y] = res;\n//         return res;\n//     }\n\n//     double knightProbability(int n, int k, int row, int col) {\n//         if (k == 0) {\n//             return 1.0;\n//         }\n\n//         // Initialize the memoization table with 0\n//         memset(memo, 0, sizeof(memo));\n\n//         double ans = solve(n, k, row, col, 1.0);\n//         return ans;\n//     }\n// };\n\n\n// class Solution {\n// public:\n//     int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};\n//     int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};\n\n//     double knightProbability(int n, int k, int row, int col) {\n//         vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n,vector<double>(n, 0.0)));\n//         dp[0][row][col] = 1.0;\n//         for (int m = 1; m <= k; m++) {\n//             for (int x = 0; x < n; x++) {\n//                 for (int y = 0; y < n; y++) {\n//                     for (int i = 0; i < 8; i++) {\n//                         int nx = x + dx[i];\n//                         int ny = y + dy[i];\n\n//                         if (nx >= 0 && nx < n && ny >= 0 && ny < n) {\n//                             dp[m][nx][ny] += dp[m - 1][x][y] / 8.0;\n//                         }\n//                     }\n//                 }\n//             }\n//         }\n\n//         double ans = 0.0;\n//         for (int x = 0; x < n; x++) {\n//             for (int y = 0; y < n; y++) {\n//                 ans += dp[k][x][y];\n//             }\n//         }\n\n//         return ans;\n//     }\n// };\n\n\n// class Solution {\n// public:\n//     int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};\n//     int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};\n\n//     double knightProbability(int n, int k, int row, int col) {\n//         vector<vector<double>> dp1(n, vector<double>(n, 0.0));\n//         vector<vector<double>> dp2(n, vector<double>(n, 0.0));\n\n//         dp1[row][col] = 1.0;\n\n//         for (int m = 1; m <= k; m++) {\n//             for (int x = 0; x < n; x++) {\n//                 for (int y = 0; y < n; y++) {\n//                     for (int i = 0; i < 8; i++) {\n//                         int nx = x + dx[i];\n//                         int ny = y + dy[i];\n\n//                         if (nx >= 0 && nx < n && ny >= 0 && ny < n) {\n//                             dp2[nx][ny] += dp1[x][y] / 8.0;\n//                         }\n//                     }\n//                 }\n//             }\n//             dp1 = dp2;\n//             dp2 = vector<vector<double>>(n,vector<double>(n, 0.0));\n//         }\n\n//         double ans = 0.0;\n//         for (int x = 0; x < n; x++) {\n//             for (int y = 0; y < n; y++) {\n//                 ans += dp1[x][y];\n//             }\n//         }\n\n//         return ans;\n//     }\n// };\n\n// class Solution {\n// public:\n//     int dy[8] = {1, -1, 2, -2, 1, -1, 2, -2};\n//     int dx[8] = {2, 2, 1, 1, -2, -2, -1, -1};\n\n//     bool isValid(int x, int y, int n) {\n//         if (x >= 0 && x < n && y >= 0 && y < n) {\n//             return true;\n//         }\n//         return false;\n//     }\n\n//     double dp[101][101][101]; // Adjust size based on the given constraints\n\n//     double solve(int n, int k, int x, int y, double prob) {\n//         if (k == 0) {\n//             return 1;\n//         }\n\n//         if (dp[k][x][y] != 0) {\n//             return dp[k][x][y];\n//         }\n\n//         double res = 0;\n//         for (int i = 0; i < 8; i++) {\n//             int nx = x + dx[i];\n//             int ny = y + dy[i];\n\n//             if (isValid(nx, ny, n)) {\n//                 res += (solve(n, k - 1, nx, ny, prob / 8.0)) / 8.0;\n//             }\n//         }\n\n//         dp[k][x][y] = res;\n//         return res;\n//     }\n\n//     double knightProbability(int n, int k, int row, int col) {\n//         if (k == 0) {\n//             return 1.0;\n//         }\n\n//         // Initialize the memoization table with 0\n//         memset(dp, 0, sizeof(dp));\n\n//         double ans = solve(n, k, row, col, 1.0);\n//         return ans;\n//     }\n// };\n\n\n\n\nclass Solution {\npublic:\n    int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};\n    int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};\n\n    double knightProbability(int n, int k, int row, int col) {\n        vector<vector<double>> dp(n, vector<double>(n, 0.0));\n\n        dp[row][col] = 1.0;\n\n        for (int m = 1; m <= k; m++) {\n            vector<vector<double>> new_dp(n,vector<double>(n, 0.0));\n            for (int x = 0; x < n; x++) {\n                for (int y = 0; y < n; y++) {\n                    for (int i = 0; i < 8; i++) {\n                        int nx = x + dx[i];\n                        int ny = y + dy[i];\n\n                        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {\n                            new_dp[nx][ny] += dp[x][y] / 8.0;\n                        }\n                    }\n                }\n            }\n            dp = move(new_dp);\n        }\n\n        double ans = 0.0;\n        for (int x = 0; x < n; x++) {\n            for (int y = 0; y < n; y++) {\n                ans += dp[x][y];\n            }\n        }\n\n        return ans;\n    }\n};\n\n\n\n\n```
['Dynamic Programming', 'Memoization', 'C++']