Evolve from recursive to dp,beats 94%
recursive version(TLE):\n\nclass Solution {\n    private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};\n    public double k
recursive version(TLE):\n```\nclass Solution {\n    private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};\n    public double knightProbability(int N, int K, int r, int c) {\n        return find(N,K,r,c);\n    }\n    public double find(int N,int K,int r,int c){\n        if(r < 0 || r > N - 1 || c < 0 || c > N - 1) return 0;\n        if(K == 0)  return 1;\n        double rate = 0;\n        for(int i = 0;i < dir.length;i++){\n            rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);\n        }\n        return rate;\n    }\n}\n```\n\ndp version:\n```\nclass Solution {\n    private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};\n    private double[][][] dp;\n    public double knightProbability(int N, int K, int r, int c) {\n        dp = new double[N][N][K + 1];\n        return find(N,K,r,c);\n    }\n    public double find(int N,int K,int r,int c){\n        if(r < 0 || r > N - 1 || c < 0 || c > N - 1) return 0;\n        if(K == 0)  return 1;\n        if(dp[r][c][K] != 0) return dp[r][c][K];\n        double rate = 0;\n        for(int i = 0;i < dir.length;i++)   rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);\n        dp[r][c][K] = rate;\n        return rate;\n    }\n}\n```
[]