# Minimum Time to Finish the Race
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-time-to-finish-the-race)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-finish-the-race
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute-force Recursion
This approach uses a recursive function to explore all possible ways to finish the race. For a given number of laps `n`, it tries all possible lengths `k` for the first "stint" (a sequence of laps on a single tire). It calculates the time for this stint of `k` laps, adds the `changeTime`, and recursively calls the function for the remaining `n-k` laps. The base case is when there are no laps left. This method explores many redundant subproblems, leading to very high time complexity.
**Time:** O(T*C + 2^numLaps) · **Space:** O(numLaps)
**Pros:** Simple to conceptualize and implement.; Directly models the decision-making process described in the problem.
**Cons:** Extremely inefficient due to exponential time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.; Calculates the same subproblems multiple times, leading to a lot of wasted computation.
### Explanation
The brute-force recursive approach directly translates the problem's choices into a recursive structure. We define a function `solve(n)` that computes the minimum time for `n` laps. To compute `solve(n)`, we consider two main scenarios:

1.  **Single Stint:** We complete all `n` laps using a single tire without any changes. The time for this is the minimum time to run `n` consecutive laps, which we can precompute as `bestStint[n]`.
2.  **Multiple Stints:** We complete the first stint of `k` laps (where `1 <= k < n`), then pay the `changeTime`, and then recursively find the minimum time for the remaining `n-k` laps. We try this for all possible values of `k`.

The final answer for `solve(n)` is the minimum over all these possibilities. This method is simple to understand but computationally expensive because `solve(m)` for a given `m` will be called many times with the same input, leading to an exponential number of total calls.

```java
// Note: This is a conceptual example. A pure recursive solution
// would be too slow. It's presented to illustrate the concept
// before optimizing with memoization or DP.
class Solution {
    long[] bestStint;
    int changeTime;

    // Precomputation of bestStint would be done here...

    private long solve(int laps) {
        if (laps == 0) {
            return 0;
        }

        // Option 1: Run all 'laps' in one stint
        long minTime = (laps < bestStint.length) ? bestStint[laps] : Long.MAX_VALUE;

        // Option 2: Run k laps, change, then solve for laps-k
        for (int k = 1; k < laps; k++) {
            if (k < bestStint.length && bestStint[k] != Long.MAX_VALUE) {
                long recursiveResult = solve(laps - k);
                if (recursiveResult != Long.MAX_VALUE) {
                    long time = bestStint[k] + this.changeTime + recursiveResult;
                    minTime = Math.min(minTime, time);
                }
            }
        }
        return minTime;
    }
}
```
### Algorithm
- Precompute an array `bestStint` where `bestStint[k]` stores the minimum time to complete `k` consecutive laps using any single tire. This is a necessary pre-step for any recursive or dynamic programming solution.
- Define a recursive function, say `solve(lapsRemaining)`, that calculates the minimum time to finish the given number of laps.
- **Base Case:** If `lapsRemaining` is 0, the time taken is 0. Return 0.
- **Recursive Step:** For `n` laps remaining, explore all possibilities for the next stint:
  - Iterate `k` from 1 to `n`.
  - The cost for a stint of `k` laps followed by a change is `bestStint[k] + changeTime + solve(n - k)`.
  - The cost for completing all `n` laps in a single stint (no change) is `bestStint[n]`.
  - The function returns the minimum of all these possibilities.
- The initial call is `solve(numLaps)`, but the logic needs to be slightly adjusted to handle the fact that the first stint does not incur a `changeTime`.
- A clearer recursive formulation is `solve(n) = min(bestStint[n], min_{1 <= k < n} (bestStint[k] + changeTime + solve(n-k)))`.

## Dynamic Programming
This approach solves the problem efficiently by using dynamic programming. It avoids the redundant computations of the recursive approach by storing the results of subproblems. We define `dp[i]` as the minimum time required to complete `i` laps. We compute `dp[i]` for `i = 1, 2, ..., numLaps`.

To find `dp[i]`, we consider all possible lengths of the final stint of laps. If the final stint has length `k`, it means we previously completed `i-k` laps in an optimal time `dp[i-k]`, then paid a `changeTime` cost, and finally ran the last `k` laps. The cost for these last `k` laps is precomputed as `bestStint[k]`. By iterating through all possible split points, we find the minimum time for `i` laps.
**Time:** O(T * C + numLaps^2) · **Space:** O(numLaps)
**Pros:** Guarantees finding the optimal solution.; Efficient enough to pass the given constraints.; Systematically builds the solution, avoiding re-computation.
**Cons:** The O(numLaps^2) complexity might be too slow if the `numLaps` constraint were significantly larger.
### Explanation
The core of this method is to build up the solution for `n` laps from the solutions for fewer laps. Let `dp[i]` be the minimum time to finish `i` laps.

First, we precompute an array `bestStint` where `bestStint[k]` is the minimum time to run `k` consecutive laps using any single tire. This is done by iterating through all available tires and simulating their performance for an increasing number of laps. Since lap times grow exponentially (`r >= 2`), a single tire is only optimal for a relatively small number of consecutive laps before it's better to switch. We can prune the simulation for a tire once its next lap time exceeds `changeTime + f` (cost to switch to a fresh tire of the same type).

After precomputation, we build the `dp` table:
- `dp[0] = 0` (0 laps take 0 time).
- For `i` from 1 to `numLaps`, `dp[i]` is the minimum of:
  1. `bestStint[i]`: The time to run all `i` laps in one go, without changing tires.
  2. `dp[j] + changeTime + bestStint[i-j]` for all `1 <= j < i`: The time to finish `j` laps optimally, pay the `changeTime`, and then run the remaining `i-j` laps in a single stint.

By filling the `dp` table this way, `dp[numLaps]` will hold the minimum time for the entire race.

```java
import java.util.Arrays;

class Solution {
    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        // bestStint[k] = min time to run k consecutive laps with one tire
        long[] bestStint = new long[numLaps + 1];
        Arrays.fill(bestStint, Long.MAX_VALUE);

        // Precompute bestStint array
        for (int[] tire : tires) {
            long f = tire[0];
            long r = tire[1];
            long currentLapTime = f;
            long totalStintTime = 0;

            for (int k = 1; k <= numLaps; k++) {
                totalStintTime += currentLapTime;
                
                // A very large total time is not useful and can overflow.
                // The max possible answer is roughly numLaps * (max_f + changeTime) ~ 2*10^8.
                if (totalStintTime > 2_000_000_000L) { 
                    break;
                }

                bestStint[k] = Math.min(bestStint[k], totalStintTime);
                
                currentLapTime *= r;
                // Optimization: if the next lap is more expensive than changing + one lap with this same tire type
                if (currentLapTime > changeTime + f) {
                    break;
                }
            }
        }

        // dp[i] = min time to finish i laps
        long[] dp = new long[numLaps + 1];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= numLaps; i++) {
            // Option 1: Run all i laps in one stint
            if (i < bestStint.length) {
                dp[i] = bestStint[i];
            }

            // Option 2: Run j laps, change, then run i-j laps in the last stint
            for (int j = 1; j < i; j++) {
                if (dp[j] != Long.MAX_VALUE && (i - j) < bestStint.length && bestStint[i - j] != Long.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + changeTime + bestStint[i - j]);
                }
            }
        }

        return (int) dp[numLaps];
    }
}
```
### Algorithm
- **Precomputation:**
  1. Create an array `bestStint` of size `numLaps + 1`, initialized with a large value. This array will store the minimum time to complete `k` consecutive laps on a single tire.
  2. Iterate through each tire `[f, r]` in the input `tires`.
  3. For each tire, calculate the cumulative time for `k=1, 2, ...` consecutive laps. Update `bestStint[k]` with the minimum time found.
  4. We can optimize this by stopping the calculation for a tire once a single lap's time becomes excessively large (e.g., greater than `changeTime + f`), as it would always be better to switch tires.
- **Dynamic Programming:**
  1. Create a DP array `dp` of size `numLaps + 1`, initialized with a large value. Set `dp[0] = 0`.
  2. Iterate `i` from 1 to `numLaps` to compute `dp[i]`.
  3. For each `i`, consider two possibilities to achieve the minimum time:
     a. Complete all `i` laps in a single stint. The time is `bestStint[i]`. So, initialize `dp[i] = bestStint[i]`.
     b. Complete the race in multiple stints. The last stint has some length `k` (`1 <= k < i`). This means we completed `i-k` laps, paid `changeTime`, and then ran the last `k` laps. The time is `dp[i-k] + changeTime + bestStint[k]`. We check this for all possible previous completion points `j = i-k`.
  4. The DP transition is: `dp[i] = min(dp[i], dp[j] + changeTime + bestStint[i-j])` for `1 <= j < i`.
  5. The final answer is `dp[numLaps]`.

# Solutions
### Java

```java
class Solution {
public
  int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
    final int inf = 1 << 30;
    int[] cost = new int[18];
    Arrays.fill(cost, inf);
    for (int[] e : tires) {
      int f = e[0], r = e[1];
      int s = 0, t = f;
      for (int i = 1; t <= changeTime + f; ++i) {
        s += t;
        cost[i] = Math.min(cost[i], s);
        t *= r;
      }
    }
    int[] f = new int[numLaps + 1];
    Arrays.fill(f, inf);
    f[0] = -changeTime;
    for (int i = 1; i <= numLaps; ++i) {
      for (int j = 1; j < Math.min(18, i + 1); ++j) {
        f[i] = Math.min(f[i], f[i - j] + cost[j]);
      }
      f[i] += changeTime;
    }
    return f[numLaps];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumFinishTime(vector<vector<int>> &tires, int changeTime,
                        int numLaps) {
    int cost[18];
    memset(cost, 0x3f, sizeof(cost));
    for (auto &e : tires) {
      int f = e[0], r = e[1];
      int s = 0;
      long long t = f;
      for (int i = 1; t <= changeTime + f; ++i) {
        s += t;
        cost[i] = min(cost[i], s);
        t *= r;
      }
    }
    int f[numLaps + 1];
    memset(f, 0x3f, sizeof(f));
    f[0] = -changeTime;
    for (int i = 1; i <= numLaps; ++i) {
      for (int j = 1; j < min(18, i + 1); ++j) {
        f[i] = min(f[i], f[i - j] + cost[j]);
      }
      f[i] += changeTime;
    }
    return f[numLaps];
  }
};

```

### Python

```python
class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int: cost = [inf] * 18 for f, r in tires: i, s, t = 1, 0, f while t <= changeTime + f: s += t cost[i] = min(cost[i], s) t *= r i += 1 f = [inf] * (numLaps + 1) f[0] = - changeTime for i in range(1, numLaps + 1): for j in range(1, min(18, i + 1)): f[i] = min(f[i], f[i - j] + cost[j]) f[i] += changeTime return f[numLaps]

```