0688.cpp (740B)
1 class Solution { 2 bool valid(int n, int x, int y) { return x >= 0 && y >= 0 && x < n && y < n; } 3 4 double dp[25][25][101]; 5 6 public: 7 double knightProbability(int n, int k, int row, int column) { 8 static const int offset_x[] = {-2, -2, -1, 1, 2, 2, 1, -1}; 9 static const int offset_y[] = {-1, 1, 2, 2, 1, -1, -2, -2}; 10 11 if (!k) return 1; 12 if (dp[row][column][k]) return dp[row][column][k]; 13 14 double res = 0; 15 for (int i = 0; i < 8; i++) { 16 int x = row + offset_x[i]; 17 int y = column + offset_y[i]; 18 19 if (!valid(n, x, y)) continue; 20 res += 0.125 * knightProbability(n, k - 1, x, y); 21 }; 22 23 return dp[row][column][k] = res; 24 } 25 };