# 2188. Minimum Time to Finish the Race    ## Approach 1: Two variables

• Time: $O(|\texttt{tires}| + \texttt{numLaps}^2)$
• Space: $O(\texttt{numLaps})$
  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] := the minimum time to finish i laps without changing tire vector singleTire(numLaps + 1, INT_MAX / 2); // dp[i] := the minimum 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]; const int r = tires[i]; int sumSecs = 0; int rPower = 1; for (int j = 1; j <= numLaps; ++j) { // the time to use the same tire for the next lap >= // the 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; 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] := the minimum time to finish i laps without changing tire int[] singleTire = new int[numLaps + 1]; // dp[i] := the minimum 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]; final int r = tires[i]; int sumSecs = 0; int rPower = 1; for (int j = 1; j <= numLaps; ++j) { // the time to use the same tire for the next lap >= // the 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; 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] := the minimum time to finish i laps without changing tire singleTire = [math.inf] * (numLaps + 1) # dp[i] := the minimum 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): # the time to use the same tire for the next lap >= # the 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 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 

## Approach 2: One variable

• Time: $O(|\texttt{tires}| \log \texttt{numLaps} + \texttt{numLaps}^2)$
• Space: $O(\texttt{numLaps})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: int minimumFinishTime(vector>& tires, int changeTime, int numLaps) { // dp[i] := the minimum time of the first i laps vector dp(numLaps + 1, INT_MAX); for (const vector& t : tires) for (int seconds = t, secondsSum = t, lapCount = 1; seconds < t + changeTime && lapCount < dp.size(); seconds *= t, ++lapCount, secondsSum += seconds) dp[lapCount] = min(secondsSum, dp[lapCount]); for (int i = 2; i <= numLaps; ++i) for (int j = 1; j * 2 <= i; ++j) dp[i] = min(dp[i], dp[j] + dp[i - j] + changeTime); return dp[numLaps]; } };