C++ DP solution


  • 0
    M
    class Solution {
    public:
        array<array<int, 2>, 8> steps = {{{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}};
        
        double helper(int N, int K, int r, int c, vector<vector<vector<double>>> &dp) {
            if (K < 0 || r < 0 || r >= N || c < 0 || c >= N)
                return 0;
            if (dp[r][c][K] != -1)
                return dp[r][c][K];
    
            dp[r][c][K] = 0;
            for (int i=0; i<8; i++) {
                dp[r][c][K] += 0.125 * helper(N, K-1, r+steps[i][0], c+steps[i][1], dp);
            }
            return dp[r][c][K];
        }
        
        double knightProbability(int N, int K, int r, int c) {
            vector<vector<vector<double>>> dp(N, vector<vector<double>>(N, vector<double>(K+1, -1)));
            for (int i=0; i<N; i++) {
                for (int j=0; j<N; j++)
                    dp[i][j][0] = 1;
            }
            
            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.