leetcode

0 class Solution {

1 static const int MOD = 1e9 + 7;

2

3 public:

4 int knightDialer(int n) const {

5 static const vector<int> offsets[] = {{4, 6}, {8, 6}, {7, 9}, {4, 8}, {3, 9, 0},

6 {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};

7

8 vector<int> pdp(10, 1), dp(10);

9 for (int i = 1; i < n; i++) {

10 for (int j = 0; j < 10; j++) {

11 int res = 0;

12 for (const int prev : offsets[j])

13 res = (res + pdp[prev]) % MOD;

14 dp[j] = res;

15 }

16 swap(dp, pdp);

17 }

18 return accumulate(begin(pdp), end(pdp), 0, [&](int a, int acc) { return (acc + a) % MOD; });

19 }

20 };