Easiest Way to Approach a DP Problem in CPP
Approach\nfirst find all the possible ways that are stored in vector of pair in my code. Then use recursion for find probability of all that recursive calls the
# Approach\nfirst find all the possible ways that are stored in vector of pair in my code. Then use recursion for find probability of all that recursive calls then return the ans that is divided by total steps;\n\nTo avoid TLE : use 3d vector to store all the recursive call\'s probabilities.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<pair<int, int>> v{{1, -2}, {1, 2}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {-2, -1}, {-2, 1}};\n    double solve(int n, int k, int row, int col, vector<vector<vector<double>>>& dp){\n        if((row<0 || row>=n) || (col<0 || col>=n))\n            return 0;\n\n        if(k==0)\n            return 1;\n\n        if(dp[row][col][k] !=0)\n            return dp[row][col][k];\n\n        double main = 0;\n        for(auto i : v){\n            int nr = row+i.first;\n            int nc = col+i.second;\n            main += solve(n, k-1, nr, nc, dp);\n        }\n\n        return dp[row][col][k] = main/8;\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)));\n        double poss = solve(n, k, row, column, dp);\n        return poss;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']