C++✅✅ | Faster🚀 than 90%🔥|Very Easy to understand
Intuition\n\nThe problem is to find the probability of a knight staying on the chessboard after making \'k\' moves starting from a given position (row, col). We
# Intuition\n\nThe problem is to find the probability of a knight staying on the chessboard after making \'k\' moves starting from a given position (row, col). We can use dynamic programming with memoization to efficiently calculate the probability.\n\n\n\n# Approach\n1. We will use dynamic programming with memoization to store the results of subproblems.\n2. The recursive function \'solve\' calculates the probability of the knight staying on the chessboard after making \'k\' moves starting from the given position (row, col).\n3. For each move of the knight, we consider all 8 possible moves and calculate their respective probabilities.The probability for each move is 0.125 (1/8) since there are 8 possible moves in total.\n4. We sum up the probabilities for all 8 moves to get the final probability for the current position and remaining moves (k-1).\n5. The base cases of the recursion are when the knight moves out of the chessboard or when no more moves are left (k=0).\n6. The function returns 1 when no more moves are left (k=0) since the knight is guaranteed to stay on the board after making 0 moves.\n\n# Complexity\n- Time complexity:\nLet \'n\' be the size of the chessboard (n x n).\nThe function \'solve\' is called for each cell in the chessboard (n x n) with \'k\' remaining moves.\nFor each cell, we explore 8 possible moves.\nTherefore, the time complexity is O(n^2 * k).\n\n- Space complexity:\nWe are using a 3D DP array of size n x n x (k + 1) to store the results of subproblems.\nThe space complexity is O(n^2 * k) for the DP array.\nAdditionally, there is a recursive call stack that can go up to \'k\'.\nSo, the overall space complexity is O(n^2 * k).\n\n# Code\n```\nclass Solution {\npublic:\n    // Function to calculate the probability of a knight staying on the chessboard after \'k\' moves.\n    double knightProbability(int n, int k, int row, int col) {\n        // Create a 3D DP array to store the results of subproblems.\n        // dp[row][col][moves] will store the probability of the knight staying at position (row, col) after \'moves\' moves.\n        vector<vector<vector<double>>> dp(n, vector<vector<double>>(n, vector<double>(k + 1, -1)));\n        return solve(n, row, col, k, dp);\n    }\n\n    // Recursive function to calculate the probability of a knight staying on the chessboard.\n    double solve(int n, int row, int col, int k, vector<vector<vector<double>>>& dp) {\n        // Base case 1: If the knight moves out of the chessboard, return 0.\n        if (row < 0 || row >= n || col < 0 || col >= n || k < 0) {\n            return 0;\n        }\n        // Base case 2: If no more moves are left (k=0), return 1. The knight is guaranteed to stay on the board after making 0 moves.\n        if (k == 0) {\n            return 1;\n        }\n        // If the probability for this position and \'k\' moves is already calculated, return it from the DP array.\n        if (dp[row][col][k] != -1) {\n            return dp[row][col][k];\n        }\n\n        // Array representing possible changes in row and column positions for a knight\'s move.\n        int delrow[8] = { -2, -2, -1, +1, +2, +2, +1, -1 };\n        int delcol[8] = { -1, +1, +2, +2, +1, -1, -2, -2 };\n\n        double ans = 0;\n        // Calculate the probability of the knight staying on the chessboard after \'k-1\' moves from all 8 possible moves.\n        for (int i = 0; i < 8; i++) {\n            int nrow = delrow[i] + row; // New row position after the move.\n            int ncol = delcol[i] + col; // New column position after the move.\n            ans += (0.125 * solve(n, nrow, ncol, k - 1, dp)); // Each move has a probability of 0.125 (1/8).\n        }\n\n        // Memoize the result and return the probability for this position and \'k\' moves.\n        return dp[row][col][k] = ans;\n    }\n};\n\n```
['Dynamic Programming', 'Memoization', 'C++']