C++✅✅ | Faster than 90% of Sol^n 🚀 | DFS + DP 🔥| Clean , Concise and Well Explained😇🎗️
CONNECT WITH ME ON LINKEDIN : https://www.linkedin.com/in/kunal-shaw-/\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nFor every p
**CONNECT WITH ME ON LINKEDIN : https://www.linkedin.com/in/kunal-shaw-/**\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor every possible valid place there is an addition of (1/8)th part of that ans.\nFor example if n = 3, k = 2, row = 0, col = 0\n-> its go to (1,2) and (2,1) by taking val of (1/8)=0.125 other moves are unvalid\n-> from (1,2) or (2,1) it can have only 2 valid move which make the ans -> (0.125/2);\n\n\n# Code\n```\nclass Solution {\npublic:\n    int X[8]={ 2, 1, -1, -2, -2, -1, 1, 2 };\n    int Y[8]={ 1, 2, 2, 1, -1, -2, -2, -1 };\n    double fn(int n,int k,int row,int col,map<vector<int>,double> &mp){\n        if(k==0) return 1.0;\n        if(mp.count({row,col,k})) return mp[{row,col,k}];\n        double ans=0.0;\n        for(int i=0;i<8;i++){\n            int x=X[i]+row;\n            int y=Y[i]+col;\n            if((x>=0 and x<n) and (y>=0 and y<n)){\n                ans+=(fn(n,k-1,x,y,mp))/8.0;\n            }\n        }\n        return mp[{row,col,k}]=ans;\n    }\n    double knightProbability(int n, int k, int row, int col) {\n        map<vector<int>,double> mp;\n        return fn(n,k,row,col,mp);\n    }\n};\n```\n![memer-cat.jpg](https://assets.leetcode.com/users/images/dfc2018d-01d8-43da-9889-af2896179f15_1675779280.3429081.jpeg)\n\n
['Hash Table', 'Dynamic Programming', 'Depth-First Search', 'C++']