straight forward C++ DP


  • 0
    J
        double getValue(vector<vector<vector<double>>> &dp, int k, int i, int j, int &N){
            if(i < 0 || i >= N || j < 0 || j >= N) return 0.0;
            else return dp[k][i][j];
        }
        
        double knightProbability(int N, int K, int r, int c) {
            // dp[k][i][j]
            vector<vector<vector<double>>> dp(K+1, vector<vector<double>>(N, vector<double>(N, 0.0)));
            
            // base case
            for(int i = 0; i < N; ++i){
                for(int j = 0; j < N; ++j)
                    dp[0][i][j] = 1.0;
            }
            
            // dp
            for(int k = 1; k <= K; ++k){
               for(int i = 0; i < N; ++i){
                    for(int j = 0; j < N; ++j){
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i-1, j-2, N);
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i-2, j-1, N);
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i-2, j+1, N);
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i-1, j+2, N);
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i+1, j-2, N);
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i+2, j-1, N);
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i+2, j+1, N);
                        dp[k][i][j] += 0.125 * getValue(dp, k-1, i+1, j+2, N);
                    } // for i
                } // for j
            }// for k      
            return dp[K][r][c];
        }
    

Log in to reply
 

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