My accepted DP solution


  • 12
    S
    int[][] moves = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
    public double knightProbability(int N, int K, int r, int c) {
        int len = N;
        double dp0[][] = new double[len][len];
        for(double[] row : dp0) Arrays.fill(row, 1);
        for(int l = 0; l < K; l++) {
            double[][] dp1 = new double[len][len];
            for(int i = 0; i < len; i++) {
                for(int j = 0; j < len; j++) {
                    for(int[] move : moves) {
                        int row = i + move[0];
                        int col = j + move[1];
                        if(isLegal(row, col, len)) dp1[i][j] += dp0[row][col];
                    }
                }
            }
            dp0 = dp1;
        }
        return dp0[r][c] / Math.pow(8, K); 
    }
    private boolean isLegal(int r, int c, int len) {
        return r >= 0 && r < len && c >= 0 && c < len;
    }
    

  • 0
    T

    great solution! very easy to understand!!!


  • 0
    S

    @szlghl1 elegant solution!


  • 1
    A

    I have a little trouble understanding what dp0 represents. Why is dp0[][] initialized with 1s? I'm thinking of dp[r][c] = 1 and the rest are 0.


  • 0
    S

    @avlgood-foxmail-com Naively the dp is a 3-dimensional array. But we only need the previous one to derive the current one, so I only preserve the previous one in the dp0 and calculate the current one in the dp1.

    Let's think about our formula, dp1[i][j] = sum(dp0[all reachable spots]). Assuming we are calculating the first step and all reachable spots are within the chessboard. Then the dp should be 8, which implies the initializing value should be 1.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.