leetcode

0 class Solution {

1 bool valid(int n, int x, int y) { return x >= 0 && y >= 0 && x < n && y < n; }

2

3 double dp[25][25][101];

4

5 public:

6 double knightProbability(int n, int k, int row, int column) {

7 static const int offset_x[] = {-2, -2, -1, 1, 2, 2, 1, -1};

8 static const int offset_y[] = {-1, 1, 2, 2, 1, -1, -2, -2};

9

10 if (!k) return 1;

11 if (dp[row][column][k]) return dp[row][column][k];

12

13 double res = 0;

14 for (int i = 0; i < 8; i++) {

15 int x = row + offset_x[i];

16 int y = column + offset_y[i];

17

18 if (!valid(n, x, y)) continue;

19 res += 0.125 * knightProbability(n, k - 1, x, y);

20 };

21

22 return dp[row][column][k] = res;

23 }

24 };