# C++/Java, DP, concise solution

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

• 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.

• @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.

• @zestypanda Thanks for explaining!

• 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.

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

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

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

• @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.

• 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)

• @ahosny The reason is explained in Dynamic programming.

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

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