# straight forward C++ DP

• ``````    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];
}
``````

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