• Time:O(KN^2)
• Space:O(N^2)

## C++

``````class Solution {
public:
double knightProbability(int N, int K, int r, int c) {
constexpr double kProb = 0.125;
const vector<pair<int, int>> dirs{{-2, 1}, {-1, 2}, {1, 2},   {2, 1},
{2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

// dp[i][j] := probability to stand on (i, j)
vector<vector<double>> dp(N, vector<double>(N));
dp[r][c] = 1.0;

for (int k = 0; k < K; ++k) {
vector<vector<double>> newDp(N, vector<double>(N));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (dp[i][j] > 0.0) {
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x >= N || y < 0 || y >= N)
continue;
newDp[x][y] += dp[i][j] * kProb;
}
}
dp = move(newDp);
}

return accumulate(begin(dp), end(dp), 0.0,
[](double s, vector<double>& row) {
return s + accumulate(begin(row), end(row), 0.0);
});
}
};
``````

## JAVA

``````class Solution {
public double knightProbability(int N, int K, int r, int c) {
final double kProb = 0.125;
final int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

// dp[i][j] := probability to stand on (i, j)
double[][] dp = new double[N][N];
dp[r][c] = 1.0;

for (int k = 0; k < K; ++k) {
double[][] newDp = new double[N][N];
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (dp[i][j] > 0.0) {
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x >= N || y < 0 || y >= N)
continue;
newDp[x][y] += dp[i][j] * kProb;
}
}
dp = newDp;
}

double ans = 0.0;

for (double[] row : dp)
ans += Arrays.stream(row).sum();

return ans;
}
}
``````

## Python

``````class Solution:
def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
dirs = [(1, 2), (2, 1), (2, -1), (1, -2),
(-1, -2), (-2, -1), (-2, 1), (-1, 2)]

# dp[i][j] := probability to stand on (i, j)
dp = [[0] * N for _ in range(N)]
dp[r][c] = 1

for _ in range(K):
newDp = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
for dx, dy in dirs:
x = i + dx
y = j + dy
if 0 <= x < N and 0 <= y < N:
newDp[i][j] += dp[x][y]
dp = newDp

return sum(map(sum, dp)) / 8**K
``````