C++/Java, DP, concise solution
For this problem, I think memoization is more optimal than direct DP. The reason is that memoization can avoid a lot of unnecessary subproblems. \nThe runtime i
For this problem, I think memoization is more optimal than direct DP. The reason is that memoization can avoid a lot of unnecessary subproblems. \nThe runtime is O(KN^2).\n\nC++ \n```\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        vector<vector<vector<double>>> dp(K+1, vector<vector<double>>(N, vector<double>(N, -1.0)));\n        return helper(dp, N, K, r, c)/pow(8, K);\n    }\nprivate:\n    double helper(vector<vector<vector<double>>>& dp, int N, int k, int r, int c) {\n        // if out of board, return 0.0\n        if (r < 0 || r >= N || c < 0 || c >= N) return 0.0;\n        // when k = 0, no more move, so it's 100% safe\n        if (k == 0) return 1.0;\n        if (dp[k][r][c] != -1.0) return dp[k][r][c];\n        dp[k][r][c] = 0.0;\n        for (int i = -2; i <= 2; i++) {\n            if (i == 0) continue;\n            dp[k][r][c] += helper(dp, N, k-1, r+i, c+3-abs(i)) + helper(dp, N, k-1, r+i, c-(3-abs(i)));\n        }      \n        return dp[k][r][c];\n    }\n};\n```\nJava\n```\nclass Solution {\n    int[][] moves = {{1,2},{1,-2},{-1,2},{-1,-2},{2,-1},{2,1},{-2,-1},{-2,1}};\n    public double knightProbability(int N, int K, int r, int c) {\n        double[][][] dp = new double[K+1][N][N];\n        return helper(dp, N, K, r, c)/Math.pow(8.0, K);\n    }\n    private double helper(double[][][] dp, int N, int k, int r, int c) {\n        if (r < 0 || r >= N || c < 0 || c >= N) return 0.0;\n        if (k == 0) return 1.0;\n        if (dp[k][r][c] != 0.0) return dp[k][r][c];\n        for (int i = 0; i < 8; i++)  \n            dp[k][r][c] += helper(dp, N, k-1, r+moves[i][0], c+moves[i][1]);\n        return dp[k][r][c]; \n    }\n}\n```
[]