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