Detailed thoughts of my final recursion + memorization solution
Before I start solving the problem, I noticed that the problem is asking about the probability that the knight remains on the board after it has stopped moving.
Before I start solving the problem, I noticed that the problem is asking about the probability that the knight remains on the board after it has stopped moving. In other word, the problem is a "all solution" problem, where we need to figure out all possible states after K moves. For any all solution problems, all fancy techniques such as dynamic programming, greedy... are all optimazation of brute force solution. Therefore, we can try to generate a brute force solution and try to apply some optimizations on it.\n\nWe can defines the problems to be:\nprobability that the knight remains on the board after it has stopped moving (either out of board or after k moves)\n\nfrom the definition, the base case of the problem is clear:\n\t1. The knight is out of board. (r and c of knight is not valid.) For this case, the probability of staying in the board is 0.0.\n\t2. The knight has already moved k step. For this case, the probability of staying in the board is 1.0.\n\nA knight can move 8 different ways in a certain point at the board. Therefore, any result that move 1 step from the current point will contribute 1/8 to the final probability.\n\nTherefore, a recursion solution is generated: \n\n```\nclass Solution {\n    private int[][] nexts = new int[][]{{1, 2}, {2, 1}, {1, -2}, {-2, 1}, {-1, 2}, {2, -1}, {-1, -2}, {-2, -1}};\n    public double knightProbability(int N, int K, int r, int c) {\n        if (r >= N || r < 0 || c >= N || c < 0) {\n            return 0.0;\n        } else if (K == 0) {\n            return 1.0;\n        } // two different base case\n        double result = 0.0;\n        for (int[] next : nexts) {\n            result += 0.125 * knightProbability(N, K - 1, r + next[0], c + next[1]); // each prob of result of next move contributes 1/8 to total result\n        }\n        return result;\n    }\n}\n```\n\nOf course, the solutions get TLE, since there are a lot of repeated computation. We expected that the knight will lands to a certain points for multiple of time with exactly k move left. For each time we need to calcutate sub problems again and again.\n\nTherefore, we can introduce a memorization to record down those repeated result and reduce our final running time.\n\nlet dp[r][c][k] represent the probability of the knight staying on board when the knight is currently at (r, c) with k remaining moves. Finally, a recursion + memorization solution is generated.\n\n```\nclass Solution {\n    private int[][] nexts = new int[][]{{1, 2}, {2, 1}, {1, -2}, {-2, 1}, {-1, 2}, {2, -1}, {-1, -2}, {-2, -1}};\n    public double knightProbability(int N, int K, int r, int c) {\n        double[][][] dp = 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(dp[i][j], -1.0);\n            }\n        }\n        return dfs(N, K, r, c, dp);\n    }\n    \n    private double dfs(int N, int K, int r, int c, double[][][] dp) {\n        if (r >= N || r < 0 || c >= N || c < 0) {\n            return 0.0;\n        } else if (K == 0) {\n            return 1.0;\n        } else if (dp[r][c][K] >= 0.0) {\n            return dp[r][c][K];\n        }\n        double result = 0.0;\n        for (int[] next : nexts) {\n            result += 0.125 * dfs(N, K - 1, r + next[0], c + next[1], dp);\n        }\n        dp[r][c][K] = result;\n        return result;\n    }\n}\n```\nTime complexity:\nSince there are at most k levels of recursion, and in each level there are 8 branches, final time complexity will be O(8^k);\nSpace complexity:\nSince I am using a 3D dp matrix, space complexity will be O(KN^2).
[]