688. Knight Probability in Chessboard

Link

Solution

    public double knightProbability(int N, int K, int r, int c) {
        double[][][] dp = new double[N][N][K+1];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                dp[i][j][0] = 1.0;
            }
        }
        
        return dfs(r, c, K, dp);
    }
    
    public double dfs(int r, int c, int K, double[][][] dp){
        if( r < 0 || r >= dp[0].length || c < 0 || c >= dp[0].length) return 0;
        if(dp[r][c][K] != 0) return dp[r][c][K];
        int[][] dirs = {{2,1}, {-2,1}, {2,-1}, {-2,-1}, {1,2}, {-1,2}, {1,-2},{-1,-2}};
        double ret = 0;
        for(int[] dir : dirs){
            ret += 0.125 * dfs(r+dir[0], c+dir[1], K-1, dp);
        }
        dp[r][c][K] = ret;
        return ret;
    }