DFS + Memoization with FULL explanation
Idea:\n Base condition: If k == 0, return 1.0 because the night will remain on board for sure without any movement.\n Now, make one movement to a valid position
**Idea:**\n* Base condition: If k == 0, return `1.0` because the night will remain on board for sure without any movement.\n* Now, make one movement to a valid position, so, the probability for the knight to stay on board is `1.0 / 8.0`.\n* From this new position, calculate the probability to remain on board with `k-1` movements remaining. Hence, we need to go in recursion. Multiply this answer with `1 / 8` because the events are linked. \n* Iterate over all "valid" new positions and calculate `(1 / 8) * probabilityWithK-1MovesFromNewPos`, and sum it up. Here we are adding the results rather than multiplying because the events are "mutually exclusive" from other valid positions. \n* Introduce the memoization. Because we may end up coming the same position with same number of moves remaining. if that\'s the case, return the cached result.\n\n```\nclass Solution {\n    public double knightProbability(int N, int K, int r, int c) {\n        Map<String, Double> cache = new HashMap<>();\n        int[][] dirs = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};\n        return helper(N, K, r, c, dirs, cache);\n        \n    }\n\n    private double helper(int n, int k, int r, int c, int[][] dirs, Map<String, Double> cache) {\n        if (k == 0) {\n            return 1.0;\n        }\n        \n        String key = r + "," + c + "," + k;\n        if (cache.containsKey(key)) {\n            return cache.get(key);\n        }\n        \n        double p = 0.0;\n        for (int[] dir : dirs) {\n            int nextR = r + dir[0],\n                nextC = c + dir[1];\n            \n            if (isValid(n, nextR, nextC)) {\n                p += (1.0 / 8.0) * helper(n, k-1, nextR, nextC, dirs, cache);\n            }\n        }\n        \n        cache.put(key, p);\n        return p;\n    }\n    \n    private boolean isValid(int n, int x, int y) {\n        return x >= 0  && x < n && y >= 0 && y < n;\n    }\n}\n```
[]