Minimum Time to Finish the Race LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minimumFinishTime(vector<vector<int>> &tires, int changeTime, int numLaps) {
4
    int n = tires.size();
5
    // to handle the cases where numLaps is small
6
    // without_change[i][j]: the total time to run j laps consecutively with
7
    // tire i
8
    vector<vector<int>> without_change(n, vector<int>(20, 2e9));
9
    for (int i = 0; i < n; i++) {
10
      without_change[i][1] = tires[i][0];
11
      for (int j = 2; j < 20; j++) {
12
        if ((long long)without_change[i][j - 1] * tires[i][1] >= 2e9) break;
13
        without_change[i][j] = without_change[i][j - 1] * tires[i][1];
14
      }
15
      // since we define it as the total time, rather than just the time for the
16
      // j-th lap we have to make it prefix sum
17
      for (int j = 2; j < 20; j++) {
18
        if ((long long)without_change[i][j - 1] + without_change[i][j] >= 2e9) break;
19
        without_change[i][j] += without_change[i][j - 1];
20
      }
21
    }
22

23
    // dp[x]: the minimum time to finish x laps
24
    vector<int> dp(numLaps + 1, 2e9);
25
    for (int i = 0; i < n; i++) {
26
      dp[1] = min(dp[1], tires[i][0]);
27
    }
28
    for (int x = 1; x <= numLaps; x++) {
29
      if (x < 20) {
30
        // x is small enough, so an optimal solution might never changes tires!
31
        for (int i = 0; i < n; i++) {
32
          dp[x] = min(dp[x], without_change[i][x]);
33
        }
34
      }
35
      for (int j = x - 1; j > 0 && j >= x - 18; j--) {
36
        dp[x] = min(dp[x], dp[j] + changeTime + dp[x - j]);
37
      }
38
    }
39

40
    return dp[numLaps];
41
  }
42
};