# 2188 Minimum Time to Finish the Race

You are given a 0-indexed 2D integer array `tires` where `tires[i] = [fi, ri]` indicates that the `ith` tire can finish its `xth` successive lap in `fi * ri(x-1)` seconds.

• For example, if `fi = 3` and `ri = 2`, then the tire would finish its `1st` lap in 3 seconds, its `2nd` lap in `3 * 2 = 6` seconds, its `3rd` lap in `3 * 22 = 12` seconds, etc.

You are also given an integer `changeTime` and an integer `numLaps`.

The race consists of `numLaps` laps and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire (including the current tire type) if you wait `changeTime` seconds.

Return the minimum time to finish the race.

Example 1:

``````Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
Output: 21
Explanation:
Lap 1: Start with tire 0 and finish the lap in 2 seconds.
Lap 2: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Lap 3: Change tires to a new tire 0 for 5 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds.
The minimum time to complete the race is 21 seconds.
``````

Example 2:

``````Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
Output: 25
Explanation:
Lap 1: Start with tire 1 and finish the lap in 2 seconds.
Lap 2: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 3: Change tires to a new tire 1 for 6 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 5: Change tires to tire 0 for 6 seconds then finish the lap in another 1 second.
Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds.
The minimum time to complete the race is 25 seconds.
``````

Constraints:

• `1 <= tires.length <= 105`
• `tires[i].length == 2`
• `1 <= fi, changeTime <= 105`
• `2 <= ri <= 105`
• `1 <= numLaps <= 1000`
 `````` 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 `````` ``````class Solution: def minimumFinishTime( self, tires: List[List[int]], changeTime: int, numLaps: int ) -> int: dp = [math.inf] * (numLaps + 1) for f, r in tires: cur_cost = f total_cost = f for i in range(1, numLaps + 1): if i > 16: break dp[i] = min(dp[i], total_cost) cur_cost *= r total_cost += cur_cost for i in range(1, numLaps + 1): for j in range(1, i): # if we switch tire at jth point dp[i] = min(dp[i], dp[j] + changeTime + dp[i - j]) return dp[-1] ''' Fast ''' class Solution: def minimumFinishTime( self, tires: List[List[int]], changeTime: int, numLaps: int ) -> int: tires.sort() new_tire = [] dp = [changeTime * (i-1) + tires * i for i in range(numLaps+1)] dp = 0 maxi = 0 for f, r in tires: if not new_tire or f > new_tire and r < new_tire: new_tire = [f, r] t = f i = 1 while i < numLaps and t * (r-1) < changeTime: t = t*r + f i += 1 if dp[i] > t: dp[i] = t maxi = max(i, maxi) for i in range(numLaps + 1): for j in range(min(i, maxi+1)): dp[i] = min(dp[i], dp[j] + changeTime + dp[i-j]) return dp[numLaps]``````