Simple C++ Video Solution || Probability || Recursion || Memoization
Video Solution\nhttps://youtu.be/rc2TRBwJ1RQ\n# Intuition\nThis question can be solved using the very basic defination of probability, ie Probability= Favorable
# Video Solution\nhttps://youtu.be/rc2TRBwJ1RQ\n# Intuition\nThis question can be solved using the very basic defination of probability, ie `Probability= Favorable Outcomes/ Total Outcomes`\nFor each move we can have `8` possible paths. So, for `k` moves we can have total of `pow(8,k)` paths. Therefore, `Total Outcomes=pow(8,k)`\nWe just need to find `Favorable outcomes`\n\n\n![image.png](https://assets.leetcode.com/users/images/01bd76bf-9c7b-48df-a607-dc48203f268f_1690019102.3898451.png)\n\n# Approach\n1. As we discussed above we just need to find total number of `favorable outcomes`. For this we will use recursion to find out number of `favorable outcomes`\n2. Also in order to reduce the time complexity, we will use a 3D dp vector which will store the total number of `favorable outcomes` for a given `row`, `col` and number of moves left `k`.\n3. Since we have return type of function as `double` our `total outcomes` and `favorable outcomes` are of type `double`\n4. To find `favorable outcomes` we will use a recursive function `solve`.\n5. Talking about base cases:\n    1. If boundary conditions are violated then we will simply `return 0`\n    2. If `k==0` ie no more steps are left we will `return 1` as we got one outcome.\n    3. If we already know the value corresponding to the combination of `row, col and k` we will just return it. ie if `dp[row][col][k]!=-1` then we will just `return dp[row][col][k]`\n    These are the base cases.\n6. Talking about the main case, we will have a variable `double ans=0` which will return total number of outcome later.\n7. We will iterate over all possible 8 direction which can be taken by knight. The directions are stored in form of vector of pairs of integer `dir`. We will reach the new row `nr` and new col `nc` and we will recurssive solve for `nr` and `nc` and will add the value in `ans`\n8. After that we will return value of `dp[row][col][k]=ans`\n# Complexity\n- Time complexity:\n$$O(n*n*k)$$\n\n- Space complexity:\n$$O(n*n*k)$$\n\n    **Please upvote if you liked !!!**\n\n# Code\n```\nint speedup = []{ios::sync_with_stdio(0); cin.tie(0); return 0;}();\nclass Solution {\npublic:\n    double solve(int n,int k, int row,int col,vector<vector<vector<double>>>&dp){\n        if(row<0||col<0||row>=n||col>=n){\n            return 0;\n        }\n        if(k==0){\n            return 1;\n        }\n        if(dp[row][col][k]!=-1){\n            return dp[row][col][k];\n        }\n        vector<pair<int,int>>dir={{-2,-1},{-2,1},{2,-1},{2,1},{1,2},{-1,2},{1,-2},{-1,-2}};\n        double ans=0;\n        for(auto ele:dir){\n            int nr=row+ele.first,nc=col+ele.second;\n            ans+=solve(n,k-1,nr,nc,dp);\n        }\n        return dp[row][col][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)));\n        double total_outcomes=pow(8,k);\n        double fav_outcomes=solve(n,k,row,column,dp);\n        double probability=fav_outcomes/total_outcomes;\n        return probability;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']