Minimum Time to Finish the Race LeetCode solution in Java

1
class Solution {
2
  int changeTime;
3

4
  public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
5
    this.changeTime = changeTime;
6
    int[] minTime = new int[numLaps + 1];
7
    Arrays.fill(minTime, Integer.MAX_VALUE);
8

9
    for (int[] tire : tires) {
10
      populateMinTime(tire, minTime);
11
    }
12

13
    int[] dp = new int[numLaps + 1];
14
    for (int i = 1; i <= numLaps; i++) {
15
      dp[i] =
16
          minTime[i]; // maxValue for dp[i] is Integer.MAX_VALUE, no need to worry about overflow
17
      for (int j = 1; j < i; j++) {
18
        dp[i] =
19
            Math.min(
20
                dp[i],
21
                dp[j]
22
                    + changeTime
23
                    + dp[i - j]); // it will never overflow, since dp[j] are far less than
24
        // Integer.MAX_VALUE
25
      }
26
    }
27
    return dp[numLaps];
28
  }
29

30
  private void populateMinTime(int[] tire, int[] minTime) {
31
    int sum = 0;
32
    int base = tire[0];
33
    int ex = tire[1];
34
    int spent = 1;
35
    for (int i = 1; i < minTime.length; i++) {
36
      spent = (i == 1) ? base : spent * ex;
37
      if (spent > changeTime + base) {
38
        break;
39
      } // set boundary
40
      sum += spent;
41
      minTime[i] = Math.min(minTime[i], sum);
42
    }
43
  }
44
}