EASY SOLUTION || C++ || DFS+3D DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n*n*k)\n\n- Space complexity: O(n*n*k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    double f(int i,int j,int k,int n,vector<vector<vector<double>>> &dp){\n        if(k==0) return 1.0;\n\n        if(dp[i][j][k]!=-1.0) return dp[i][j][k];\n        int dx[]={-2,-2,-1,1,2,2,1,-1},dy[]={-1,1,2,2,1,-1,-2,-2};\n        double ans = 0.0;\n        for(int t=0;t<8;t++){\n            int nx=i+dx[t],ny=j+dy[t];\n            if(nx>=0 && nx<n && ny>=0 && ny<n){\n                ans += f(nx,ny,k-1,n,dp);\n            }\n        }\n\n        return dp[i][j][k]=ans;\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.0)));\n        double ct=f(row,column,k,n,dp);\n        for(int i=0;i<k;i++){\n            ct = ct/8;\n        }\n\n        return ct;\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'C++']