C++ || Memoisation || Tabulation
Connect with me on LinkedIn: https://www.linkedin.com/in/abhay5349singh/\n\nApproach:\n Since knight can move in 8 directions, so probability of taking 1 move t
**Connect with me on LinkedIn**: https://www.linkedin.com/in/abhay5349singh/\n\n**Approach:**\n* Since knight can move in 8 directions, so probability of taking 1 move to reach next {i,j} = 1/8 = 0.125\n* Proabilties are multiplied along 1 path i.e for k consecutive moves & summed up to give total probability \n\n**Memoisation:**\n\n```\nclass Solution {\npublic:\n    \n    double memo[26][26][101];\n    int dxy[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};\n    \n    double prob(int n, int k, int r, int c){\n        if(memo[r][c][k]!=0) return memo[r][c][k];\n        \n        if(k==0) return 1; // probability of staying inside chess board after k moves\n        \n        double ans=0;\n        for(int d=0;d<8;d++){\n            int x=r+dxy[d][0], y=c+dxy[d][1];\n            \n            if(x>=0 && y>=0 && x<n && y<n) ans+=0.125*prob(n,k-1,x,y);\n        }\n        return memo[r][c][k]=ans;\n    }\n    \n    double knightProbability(int n, int k, int r, int c) {\n       return prob(n,k,r,c);\n    }\n};\n```\n\n**Tabulation:**\n\n```\nclass Solution {\npublic:\n    \n\t int dxy[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};\n\t \n    double knightProbability(int n, int k, int r, int c) { \n        double dp[26][26][101];\n        dp[r][c][0]=1; // probability of staying inside chess board initially\n        \n        for(int steps=1;steps<k+1;steps++){\n            for(int i=0;i<n;i++){\n                for(int j=0;j<n;j++){\n                    for(int d=0;d<8;d++){\n                        int x=i+dxy[d][0];\n                        int y=j+dxy[d][1];\n\n                        if(x>=0 && y>=0 && x<n && y<n){\n                            dp[i][j][steps]+=0.125*dp[x][y][steps-1];\n                        }\n                    }\n                }\n            }\n        }\n        double ans=0;\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                ans+=dp[i][j][k];\n            }\n        }\n        return ans; \n    }\n};\n```\n\n**Do Upvote If It Helps :)**
['Memoization', 'C++']