688. Knight Probability in Chessboard

Posted on | Edited on | Views:

LeetCode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Out of time limit
class Solution {   
    private int[][] dir={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
    
    public double knightProbability(int N, int K, int r, int c) {
        if(r<0||r>N-1||c<0||c>N-1) return 0;
        if(K==0) return 1;
        double rate=0;
        for(int i=0;i<dir.length;i++){
            rate+=0.125*knightProbability(N,K-1,r+dir[i][0],c+dir[i][1]);
        }
        return rate;
    } 
}

link
DP, Top Down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private int[][] dir={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
    
    private double find(int N, int K, int r, int c, double[][][] dp){
        if(r<0||r>N-1||c<0||c>N-1) return 0;
        if(K==0) return 1;
        if(dp[r][c][K]!=0) return dp[r][c][K];
        double rate=0;
        for(int i=0;i<dir.length;i++){
            rate+=0.125*find(N,K-1,r+dir[i][0],c+dir[i][1],dp);
        }
        
        return dp[r][c][K] = rate;
    }
    
    public double knightProbability(int N, int K, int r, int c) {
        return find(N,K,r,c,new double[N][N][K+1]);
    }
}

0%