Jump Game V LeetCode solution in C++

1
class Solution {
2
  vector<int> dp;
3
  int countJumps(vector<int> &arr, int i, int d) {
4
    if (dp[i] != -1) return dp[i];
5
    int jumps = 0;
6
    int k = 1;
7
    while (k <= d && k + i < arr.size()) {
8
      if (arr[k + i] < arr[i]) {
9
        jumps = max(countJumps(arr, k + i, d) + 1, jumps);
10
        k++;
11
      } else {
12
        break;
13
      }
14
    }
15
    k = 1;
16
    while (k <= d && i - k >= 0) {
17
      if (arr[i] > arr[i - k]) {
18
        jumps = max(countJumps(arr, i - k, d) + 1, jumps);
19
        k++;
20
      } else {
21
        break;
22
      }
23
    }
24
    return dp[i] = jumps;
25
  }
26

27
 public:
28
  int maxJumps(vector<int> &arr, int d) {
29
    dp.resize(arr.size(), -1);
30
    int maxJumps = 0;
31
    int n = arr.size();
32
    for (int i = 0; i < n; i++) {
33
      maxJumps = max(countJumps(arr, i, d), maxJumps);
34
    }
35
    return maxJumps + 1;
36
  }
37
};