Knight Dialer LeetCode solution in C++

1
class Solution {
2
 public:
3
  static const int mod = 1e9 + 7;
4
  vector<vector<int>> MOVES = {
5
      {4, 6}, {8, 6}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4},
6
  };
7

8
  int cache[5001][10];
9

10
  int knightDialer(int n) {
11
    vector<int> nextNumbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
12
    return knightDialer(n, nextNumbers);
13
  }
14

15
  int knightDialer(int remaining, vector<int> &nextNumbers) {
16
    if (remaining == 1) return nextNumbers.size();
17

18
    int count = 0;
19
    for (int nextNumber : nextNumbers) {
20
      int cur = cache[remaining][nextNumber];
21
      if (cur == 0) {
22
        cur = knightDialer(remaining - 1, MOVES[nextNumber]);
23
        cache[remaining][nextNumber] = cur;
24
      }
25
      count += cur;
26
      count %= mod;
27
    }
28
    return count;
29
  }
30
};