Image Solution - Recursion + Memoization
Almost every DP problem can be solved using "Recursion + Memoization" technique.\n\n# Intuition\n\nIn the following image the sign "\u2B50" denotes the knight. 
# Almost every DP problem can be solved using "Recursion + Memoization" technique.\n\n# Intuition\n\nIn the following image the sign "\u2B50" denotes the knight. Illustrate the first example test case:\n```\nInput: n = 3, k = 2, row = 0, column = 0\nOutput: 0.06250\n```\n\n![image.png](https://assets.leetcode.com/users/images/3974ef61-0906-43ff-84fd-ad1864162f90_1690056894.7522848.png)\n\n\n# Complexity\n- Time complexity: $$O(N^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N^3)$$ for 3D array.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` Java []\nclass Solution {\n    int[][] dirs = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}};\n    public double knightProbability(int n, int k, int row, int column) {\n        double[][][] memo = new double[n][n][k+1];\n        for(int i=0; i<n; i++) {\n            for(int j=0; j<n; j++) {\n                Arrays.fill(memo[i][j], -1.0);\n            }\n        }\n        return dfs(n, k, row, column, memo);\n    }\n\n    double dfs(int n, int k, int r, int c, double[][][] memo) {\n        if(r < 0 || r >= n || c < 0 || c >= n) {\n            return 0.0;\n        }\n        if(k == 0) {\n            return 1.0;\n        }\n        if(memo[r][c][k]!=-1.0) {\n            return memo[r][c][k];\n        }\n\n        double probability = 0.0;\n        double possibleEvents = 8.0;\n        for(int[] dir : dirs) {\n            probability += dfs(n, k-1, r+dir[0], c+dir[1], memo); \n        }\n\n        return memo[r][c][k] = probability/possibleEvents;\n    }\n}\n```
['Recursion', 'Memoization', 'C++', 'Java']