✅✅Faster || Easy To Understand || C++ Code
Using Recursion && Memoization\n\n Time Complexity :- O(N * N * K)\n\n Space Complexity :- O(N * N * K)\n\n\nclass Solution {\npublic:\n    \n    // declare a d
* ***Using Recursion && Memoization***\n\n* ***Time Complexity :- O(N * N * K)***\n\n* ***Space Complexity :- O(N * N * K)***\n\n```\nclass Solution {\npublic:\n    \n    // declare a dp\n    \n    double dp[30][30][105];\n    \n    // x and y co-ordinates of 8 directions\n   \n    vector<int> dx = {-2, -2, -1, 1, 2, 2, 1, -1};\n    \n    vector<int> dy = {-1, 1, 2, 2, 1, -1, -2, -2};\n    \n    double dfs(int i, int j, int n, int moves)\n    {\n        // base case if we have reached out of grid\n        \n        if(i < 0 || i >= n || j < 0 || j >= n)\n            return 0;\n        \n        // if no moves are remaining\n        \n        if(moves <= 0)\n            return 1;\n        \n        // if already calculated\n        \n        if(dp[i][j][moves] != 0)\n            return dp[i][j][moves];\n        \n        // find total possible ways of staying on chess board\n        \n        double ans = 0;\n        \n        for(int k = 0; k < 8; k++)\n        {\n            int new_row = i + dx[k];\n            \n            int new_col = j + dy[k];\n            \n            ans += dfs(new_row, new_col, n, moves - 1);\n        }\n        \n        // for each cell there are 8 possible moves, so probablity will be no. of successfull moves / 8\n        \n        // store the result and return\n        \n        return dp[i][j][moves] = ans / 8.0;\n    }\n    \n    double knightProbability(int n, int k, int row, int column) {\n        \n        // initialize the dp with 0\n        \n        memset(dp, 0, sizeof(dp));\n       \n        return dfs(row, column, n, k);\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Recursion', 'Memoization', 'C', 'C++']