Minimum Skips to Arrive at Meeting On Time LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> D;
4
  long long s, last;
5
  long long memo[1010][1010];
6
  long long dfs_with_minimum_time_with_k_skip(int idx, int k) {
7
    if (idx < 0) return 0;
8
    long long &ret = memo[idx][k];
9
    if (ret != -1) return ret;
10
    long long d = dfs_with_minimum_time_with_k_skip(idx - 1, k) + D[idx];
11
    if (d % s) d = ((d / s) + 1) * s;
12
    ret = d;
13
    if (k > 0) ret = min(ret, dfs_with_minimum_time_with_k_skip(idx - 1, k - 1) + D[idx]);
14
    return ret;
15
  }
16
  int minSkips(vector<int> &dist, int speed, int hoursBefore) {
17
    int n = dist.size();
18
    D = dist, s = speed;
19
    int lo = 0, hi = n;
20
    long long d = 0, H = hoursBefore;
21
    H *= s;
22
    last = dist[n - 1];
23
    for (int dd : dist) d += dd;
24
    memset(memo, -1, sizeof(memo));
25
    if (d / s > hoursBefore) return -1;
26
    while (lo < hi) {
27
      int mid = (lo + hi) / 2;
28
      long long h = dfs_with_minimum_time_with_k_skip(n - 2, mid) +
29
                    last; // we should start from second last since it is not
30
                          // required to rest on last road
31
      if (h <= H)
32
        hi = mid;
33
      else
34
        lo = mid + 1;
35
    }
36
    return lo == D.size() ? -1 : lo;
37
  }
38
};