Formatted question description: https://leetcode.ca/all/2188.html

# 2188. Minimum Time to Finish the Race (Hard)

You are given a **0-indexed** 2D integer array `tires`

where `tires[i] = [f`

indicates that the _{i}, r_{i}]`i`

tire can finish its ^{th}`x`

successive lap in ^{th}`f`

seconds._{i} * r_{i}^{(x-1)}

- For example, if
`f`

and_{i}= 3`r`

, then the tire would finish its_{i}= 2`1`

lap in^{st}`3`

seconds, its`2`

lap in^{nd}`3 * 2 = 6`

seconds, its`3`

lap in^{rd}`3 * 2`

seconds, etc.^{2}= 12

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 = 4Output:21Explanation: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 = 5Output:25Explanation: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 <= 10`

^{5}`tires[i].length == 2`

`1 <= f`

_{i}, changeTime <= 10^{5}`2 <= r`

_{i}<= 10^{5}`1 <= numLaps <= 1000`

**Similar Questions**:

## Solution 1. DP

The `best[i]`

is the least time we need to finish `i+1`

laps **using a single tire**. For each tire, we try to update the `best`

values with it.

The `dp`

part is doing knapsack using the `best`

values to get the total `numLaps`

laps.

```
// OJ: https://leetcode.com/problems/minimum-time-to-finish-the-race/
// Time: O(N * numLaps)
// Space: O(numLaps)
class Solution {
public:
int minimumFinishTime(vector<vector<int>>& A, int change, int numLaps) {
int N = A.size(), len = 0;
vector<long> best(numLaps, LONG_MAX), dp(numLaps + 1, INT_MAX);
for (int i = 0; i < N; ++i) {
long f = A[i][0], r = A[i][1], sum = change, p = 1; // We assume we also need `change` time to use the first tire so that we don't need to treat the first tire as a special case
for (int j = 0; j < numLaps; ++j) {
sum += f * p;
if (f * p >= f + change) break; // If using the same tire takes no less time than changing the tire, stop further using the current tire
best[j] = min(best[j], sum);
len = max(len, j + 1);
p *= r;
}
}
dp[0] = 0; // dp[i + 1] is the minimum time to finish `numLaps` laps
for (int i = 0; i < numLaps; ++i) {
for (int j = 0; j < len && i - j >= 0; ++j) { // try using the same tire in the last `j+1` laps
dp[i + 1] = min(dp[i + 1], dp[i - j] + best[j]);
}
}
return dp[numLaps] - change; // minus the `change` we added to the first tire
}
};
```