C++ 3 solutions
1.Using queue\n\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        double prob;\n        \n        queue<pair<int,i
1.Using queue\n```\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        double prob;\n        \n        queue<pair<int,int>> q;\n        q.push({r,c});\n        int drxn[]={2,1,2,-1,-2,1,-2,-1,2};\n        vector<vector<double>> dp(N+1,vector<double>(N+1));\n        dp[r][c]=1.0;\n        while(K--&&!q.empty())\n        {\n            int n=q.size();\n            int cnt=0;\n            vector<vector<double>> dp1(N+1,vector<double>(N+1));\n            for(int i=0;i<n;i++)\n            {\n                int row=q.front().first;\n                int col=q.front().second;\n                q.pop();\n                for(int j=0;j<8;j++)\n                {\n                    int x=row+drxn[j];\n                    int y=col+drxn[j+1];\n                    if(x>=0&&x<N&&y>=0&&y<N)\n                    {\n                        if(dp1[x][y]==0)\n                            q.push({x,y});\n                        dp1[x][y]+=dp[row][col]/8.0;\n                    }\n                }\n            }\n            dp=dp1;\n        }\n        for(vector<double> ans: dp)\n        {\n            for(double x:ans)\n                prob+=x;\n        }\n        return prob;\n            \n    }\n};\n```\n2.Recursion+memoization\n```\nclass Solution {\npublic:\n    double calc(int n,int k,int r,int c,vector<vector<vector<double>>>& dp, vector<int>& drxn)\n    {\n        if(k==0)\n            return dp[r][c][k]=1;\n        double ans=0;\n        if(dp[r][c][k]!=0)\n            return dp[r][c][k];\n        for(int i=0;i<8;i++)\n        {\n            int row=r+drxn[i];\n            int col=c+drxn[i+1];\n            if(row>=0&&row<n&&col>=0&&col<n)\n                ans+=calc(n,k-1,row,col,dp,drxn)/8.0;\n        }\n        // cout<<ans<<endl;\n        return dp[r][c][k]=ans;\n    }\n    double knightProbability(int N, int K, int r, int c) {\n        double prob=0;\n        vector<int> drxn{2,1,2,-1,-2,1,-2,-1,2};\n        // double dp[N+1][N+1][K+1];\n        // memset(dp,0,sizeof(dp));\n        // dp[r-1][c-1][K]=1;\n        vector<vector<vector<double>>> dp(N+1,vector<vector<double>>(N+1,vector<double>(K+1)));\n        calc(N,K,r,c,dp,drxn);\n        return dp[r][c][K];\n    }\n};\n```\n3.DP w/o recursion\n```\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        double prob=0;\n        \n        // queue<pair<int,int>> q;\n        // q.push({r,c});\n        int drxn[]={2,1,2,-1,-2,1,-2,-1,2};\n        vector<vector<double>> dp(N,vector<double>(N,0));\n        dp[r][c]=1;\n        while(K--)\n        {\n            vector<vector<double>> dp2(N,vector<double>(N,0));\n            // int n=q.size();\n            double cnt=0;\n            for(int row=0;row<N;row++)\n            {\n                for(int col=0;col<N;col++)\n                \n                {   // int row=q.front().first;\n                    // int col=q.front().second;\n                    // q.pop();\n                    for(int j=0;j<8;j++)\n                    {\n                        int x=row+drxn[j];\n                        int y=col+drxn[j+1];\n                        if(x>=0&&x<N&&y>=0&&y<N)\n                        {\n                            // if(dp[x][y]==0)\n                            //     q.push({x,y});\n                            dp2[x][y]+=(dp[row][col]/8.0);\n                        }\n                    }   \n                }\n            }\n            // prob=cnt;\n            dp=dp2;\n        }\n        for(vector<double> ans:dp)\n        {\n            for(double x:ans)\n                prob+=x;\n        }\n        return prob;\n            \n    }\n};\n```\nAny suggestions are welcome regarding improvement.
['Dynamic Programming', 'Breadth-First Search', 'Queue', 'C']