My accepted DP solution

• ``````int[][] moves = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
public double knightProbability(int N, int K, int r, int c) {
int len = N;
double dp0[][] = new double[len][len];
for(double[] row : dp0) Arrays.fill(row, 1);
for(int l = 0; l < K; l++) {
double[][] dp1 = new double[len][len];
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
for(int[] move : moves) {
int row = i + move[0];
int col = j + move[1];
if(isLegal(row, col, len)) dp1[i][j] += dp0[row][col];
}
}
}
dp0 = dp1;
}
return dp0[r][c] / Math.pow(8, K);
}
private boolean isLegal(int r, int c, int len) {
return r >= 0 && r < len && c >= 0 && c < len;
}
``````

• great solution! very easy to understand!!!

• @szlghl1 elegant solution!

• I have a little trouble understanding what dp0 represents. Why is dp0[][] initialized with 1s? I'm thinking of dp[r][c] = 1 and the rest are 0.

• @avlgood-foxmail-com Naively the dp is a 3-dimensional array. But we only need the previous one to derive the current one, so I only preserve the previous one in the dp0 and calculate the current one in the dp1.

Let's think about our formula, dp1[i][j] = sum(dp0[all reachable spots]). Assuming we are calculating the first step and all reachable spots are within the chessboard. Then the dp should be 8, which implies the initializing value should be 1.

• Want to ask why dp should be double? I set it as int and sometimes it will generate 0, even if I wrote dp[r][c] * 1.0 / Math.pow(8, K). Where will 0 come out?

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