Simple memoization solution || C++ O(n*n*k)
Just make a dp array that will store the probability of being inside board after rem moves starting from (row, col).\nIn each move we go to 8 possible next posi
Just make a dp array that will store the probability of being inside board after ```rem moves starting from (row, col)```.\nIn each move we go to 8 possible next positions and the answer is ```(addition of all their possiblities)/8```.\nDivide by 8 is done everytime as after each move we can go to 8 different positions and that make 8*more scenarios after each move, so divide by 8 each time to calculate the probability. If rem is 0 and knight is inside board probability returned is 1. (As being inside board with 0 moves remaining will always satisfy the condition)\nIf it is outside board at any point, return 0.\n(Actually the question is a bit poorly phrased)\n\nAnd like this we store probabilities and reuse from dp array if required, and reach to our answer. Easy.\n```\nclass Solution {\npublic:\n    double dfs(int n, int row, int col, int rem, vector<vector<vector<double>>>& dp){\n        if(row<0 || row>=n || col<0 || col>=n) return 0;\n        if(rem==0) return 1;\n        if(dp[row][col][rem]!=-1) return dp[row][col][rem];\n\n        double a = dfs(n,row-1,col-2,rem-1,dp);\n        double b = dfs(n,row-1,col+2,rem-1,dp);\n        double c = dfs(n,row+1,col-2,rem-1,dp);\n        double d = dfs(n,row+1,col+2,rem-1,dp);\n        double e = dfs(n,row-2,col+1,rem-1,dp);\n        double f = dfs(n,row-2,col-1,rem-1,dp);\n        double g = dfs(n,row+2,col+1,rem-1,dp);\n        double h = dfs(n,row+2,col-1,rem-1,dp);\n        dp[row][col][rem] = (a + b + c + d + e + f + g + h)/8;\n        return dp[row][col][rem];\n    }\n\n    double knightProbability(int n, int k, int row, int column) {\n        vector<vector<vector<double>>> dp(n,vector<vector<double>>(n,vector<double>(k+1,-1)));\n        return dfs(n,row,column,k,dp);\n    }\n};\n```\n# Complexity\n- Time complexity: O((n^2)*k)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O((n^2)*k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Please upvote for your continuous support \uD83D\uDE0A. If you have any doubt, feel free to comment down below, I will try my best to reply and explain. Thank you for reading my answer.
['Dynamic Programming', 'Memoization', 'C++']