C++/Java, DP, concise solution


  • 5
    Z

    For this problem, I think memoization is more optimal than direct DP. The reason is that memoization can avoid a lot of unnecessary subproblems.
    The runtime is O(KN^2).

    C++

    class Solution {
    public:
        double knightProbability(int N, int K, int r, int c) {
            vector<vector<vector<double>>> dp(K+1, vector<vector<double>>(N, vector<double>(N, -1.0)));
            return helper(dp, N, K, r, c)/pow(8, K);
        }
    private:
        double helper(vector<vector<vector<double>>>& dp, int N, int k, int r, int c) {
            // if out of board, return 0.0
            if (r < 0 || r >= N || c < 0 || c >= N) return 0.0;
            // when k = 0, no more move, so it's 100% safe
            if (k == 0) return 1.0;
            if (dp[k][r][c] != -1.0) return dp[k][r][c];
            dp[k][r][c] = 0.0;
            for (int i = -2; i <= 2; i++) {
                if (i == 0) continue;
                dp[k][r][c] += helper(dp, N, k-1, r+i, c+3-abs(i)) + helper(dp, N, k-1, r+i, c-(3-abs(i)));
            }      
            return dp[k][r][c];
        }
    };
    

    Java

    class Solution {
        int[][] moves = {{1,2},{1,-2},{-1,2},{-1,-2},{2,-1},{2,1},{-2,-1},{-2,1}};
        public double knightProbability(int N, int K, int r, int c) {
            double[][][] dp = new double[K+1][N][N];
            return helper(dp, N, K, r, c)/Math.pow(8.0, K);
        }
        private double helper(double[][][] dp, int N, int k, int r, int c) {
            if (r < 0 || r >= N || c < 0 || c >= N) return 0.0;
            if (k == 0) return 1.0;
            if (dp[k][r][c] != 0.0) return dp[k][r][c];
            for (int i = 0; i < 8; i++)  
                dp[k][r][c] += helper(dp, N, k-1, r+moves[i][0], c+moves[i][1]);
            return dp[k][r][c]; 
        }
    }
    

  • 3

    Nice solution!
    I am curious why is that when K is 100 and N is 25, there is no stack overflow. another question is why is the precision is not lost when dividing the possibilities 1, by 8, 100 times, which is 2^ 300, seems require something like a 40 bytes big decimal.


  • 1
    Z

    @alexander Thank you for the comments! Here are some of my thoughts on the questions. But I may be wrong :)
    Q1: The number of recursion levels you can do depends on the call-stack size and the size of local variables and arguments that are placed on such a stack. Theoretically current desktop machine can handle a recursive depth of hundreds to some thousands. stackoverflow
    Q2: I think the precision does get lost. Note that all possibilities in level i are summed together before division in level i+1. This may help preserve the precision, but cannot prevent it.


  • 0

    @zestypanda Thanks for explaining!


  • 1
    R

    Nice solution, one thing make the code neat is using:

    int[] dx = {-1,-2,-2,-1,1,2, 2, 1};
    int[] dy = {-2,-1, 1, 2,2,1,-1,-2};
    

    Make it an iteration rather than write 8 lines.


  • 0

    @realhly88 said in C++/Java, DP, concise solution:

    Make it an iteration rather than write 8 lines.

    Make it a single array rather than write 2 lines.
    int[][] dxy = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};


  • 0
    Z

    @wavy @realhly88 Thank you for the comments! I have updated the java version.


  • 0
    M

    @zestypanda
    I think we can also optimize the solution by handling out-of-boundary conditions right in the loop to decrease recursion depth

    
    for (int i = 0; i < 8; i += 1) {
        int x = r + moves[i][0];
        int y = c + moves[i][1];
        if (x < 0 || x >= N || y < 0 || y >= N) continue; // handle here instead of at the start
        dp[r][c][k] += dfs(dp, N, x, y, k - 1);
    }
    
    

  • 0
    Z

    @milkshakeplz Thanks for the suggestion! It definitely decrease the recursive depth by 1. It may improve the run time, but usually the difference between like 20 and 19 is subtle.


  • 0
    A

    @alexander said in C++/Java, DP, concise solution:

    ibilities 1, by 8, 100 times, which is 2^ 30

    Why the run time is O(N^2 K), the solution mainly go K recursive calls each of them explore 8 moves calls. I would say the runtime is O(8^k)


  • 0
    Z

    @ahosny The reason is explained in Dynamic programming.


  • 0
    E

    An improvement is to use (KN^2/8) space for the DP, given than the Chessboard is symmetric. (0, 0), (0, N-1), (N-1,0), (N-1, N-1) will have the same results. Here is my code, using (KN^2/4) space.

    class Solution {
        vector<pair<int, int> > dirs = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
        double helper(int N, int K, int r, int c, vector<vector<double> >& dp) {
            if (K == 0) return 1.0;
            if (r > (N - 1) / 2) r = N - r - 1;
            if (c > (N - 1) / 2) c = N - c - 1;
            int hN = (N + 1) / 2, key = r * hN + c;
            if (dp[key][K - 1] > 0.) return dp[key][K - 1];
            dp[key][K - 1] = 0.;
            for (auto d : dirs) {
                int nx = r + d.first, ny = c + d.second;
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    dp[key][K - 1] += 0.125 * helper(N, K - 1, nx, ny, dp);
                }
            }
            return dp[key][K - 1];
        }
    public:
        double knightProbability(int N, int K, int r, int c) {
            int hN = (N + 1) / 2;
            vector<vector<double> > dp = vector<vector<double> >(hN * hN, vector<double> (K, -1.0));
            return helper(N, K, r, c, dp);
        }
    };
    

Log in to reply
 

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