Java Memoization (Easy to Understand)
There are total of Math.pow(8,k) moves in available for the knight . We calculate the total moves for which the knight will stay inside the board and then calcu
There are total of Math.pow(8,k) moves in available for the knight . We calculate the total moves for which the knight will stay inside the board and then calculate the probability.\n```\nclass Solution {\n   \n    Map<String,Double> map;\n\t\n    public double knightProbability(int N, int K, int r, int c) {\n\t\n\t\tmap = new HashMap();\n\t\t\n\t\t// prob returns the total paths which stayed inside the board and then we divide it with total number of moves .\n\t\t\n       double result = prob(N,K,r,c) / Math.pow(8,K); \n        return result;\n    }\n    public double prob(int N,int K,int r,int c){\n\t// If the path is out of the board return 0 ;\n        if(r < 0 || r >= N || c < 0 || c >= N){\n            return 0;\n        }\n        String key = K +"->"+r+"->"+c;\n\t\t\n\t\t//if path is not out of the board and no moves left return 1;\n        if(K==0){\n            return 1;\n        } \n        if(map.containsKey(key))return map.get(key);\n        \n\t\t// There are total of 8 possible moves and we are traversing all the possible paths.\n\t\t\n        double op1 = prob(N,K-1,r+2,c+1);\n        double op2 = prob(N,K-1,r+2,c-1);\n        double op3 = prob(N,K-1,r-2,c+1);\n        double op4 = prob(N,K-1,r-2,c-1);\n        double op5 = prob(N,K-1,r-1,c+2);\n        double op6 = prob(N,K-1,r+1,c+2);\n        double op7 = prob(N,K-1,r+1,c-2);\n        double op8 = prob(N,K-1,r-1,c-2);\n        \n        double result = op1 + op2 + op3 + op4 + op5 + op6 + op7 + op8;\n        map.put(key , result);\n        return result;\n    }\n    \n}
['Memoization', 'Java']