My accepted DP solution


  • 13
    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!


  • 2
    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.


  • 0
    D

    Want to ask why dp should be double? I set it as int and sometimes it will generate 0, even if I wrote dp[r][c] * 1.0 / Math.pow(8, K). Where will 0 come out?


Log in to reply
 

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