# 2188. Minimum Time to Finish the Race

• Time: $O(|\texttt{tires}| + \texttt{numLaps}^2)$
• Space: $O(\texttt{numLaps}^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: int minimumFinishTime(vector>& tires, int changeTime, int numLaps) { // singleTire[i] := min time to finish i laps w/o changing tire vector singleTire(numLaps + 1, INT_MAX / 2); // dp[i] := min time to finish i laps vector dp(numLaps + 1, INT_MAX / 2); for (int i = 0; i < tires.size(); ++i) { const int f = tires[i][0]; const int r = tires[i][1]; int sumSecs = 0; int rPower = 1; for (int j = 1; j <= numLaps; ++j) { // time to use the same tire for next lap >= // time to change a new tire + f if ((long)f * rPower >= changeTime + f) break; sumSecs += f * rPower; rPower *= r; singleTire[j] = min(singleTire[j], sumSecs); } } dp[0] = 0; for (int i = 1; i <= numLaps; ++i) for (int j = 1; j <= i; ++j) dp[i] = min(dp[i], dp[i - j] + changeTime + singleTire[j]); return dp[numLaps] - changeTime; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) { // singleTire[i] := min time to finish i laps w/o changing tire int[] singleTire = new int[numLaps + 1]; // dp[i] := min time to finish i laps int[] dp = new int[numLaps + 1]; Arrays.fill(singleTire, Integer.MAX_VALUE / 2); Arrays.fill(dp, Integer.MAX_VALUE / 2); for (int i = 0; i < tires.length; ++i) { final int f = tires[i][0]; final int r = tires[i][1]; int sumSecs = 0; int rPower = 1; for (int j = 1; j <= numLaps; ++j) { // time to use the same tire for next lap >= // time to change a new tire + f if ((long) f * rPower >= changeTime + f) break; sumSecs += f * rPower; rPower *= r; singleTire[j] = Math.min(singleTire[j], sumSecs); } } dp[0] = 0; for (int i = 1; i <= numLaps; ++i) for (int j = 1; j <= i; ++j) dp[i] = Math.min(dp[i], dp[i - j] + changeTime + singleTire[j]); return dp[numLaps] - changeTime; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution: def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int: # singleTire[i] := min time to finish i laps w//o changing tire singleTire = [math.inf] * (numLaps + 1) # dp[i] := min time to finish i laps dp = [math.inf] * (numLaps + 1) for i, (f, r) in enumerate(tires): sumSecs = 0 rPower = 1 for j in range(1, numLaps + 1): # time to use the same tire for next lap >= # time to change a new tire + f if f * rPower >= changeTime + f: break sumSecs += f * rPower rPower *= r singleTire[j] = min(singleTire[j], sumSecs) dp[0] = 0 for i in range(1, numLaps + 1): for j in range(1, i + 1): dp[i] = min(dp[i], dp[i - j] + changeTime + singleTire[j]) return dp[numLaps] - changeTime