<p>You are given a <strong>0-indexed</strong> 2D integer array <code>tires</code> where <code>tires[i] = [f<sub>i</sub>, r<sub>i</sub>]</code> indicates that the <code>i<sup>th</sup></code> tire can finish its <code>x<sup>th</sup></code> successive lap in <code>f<sub>i</sub> * r<sub>i</sub><sup>(x-1)</sup></code> seconds.</p>

<ul>
	<li>For example, if <code>f<sub>i</sub> = 3</code> and <code>r<sub>i</sub> = 2</code>, then the tire would finish its <code>1<sup>st</sup></code> lap in <code>3</code> seconds, its <code>2<sup>nd</sup></code> lap in <code>3 * 2 = 6</code> seconds, its <code>3<sup>rd</sup></code> lap in <code>3 * 2<sup>2</sup> = 12</code> seconds, etc.</li>
</ul>

<p>You are also given an integer <code>changeTime</code> and an integer <code>numLaps</code>.</p>

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

<p>Return<em> the <strong>minimum</strong> time to finish the race.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
<strong>Output:</strong> 21
<strong>Explanation:</strong> 
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
<strong>Output:</strong> 25
<strong>Explanation:</strong> 
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. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= tires.length &lt;= 10<sup>5</sup></code></li>
	<li><code>tires[i].length == 2</code></li>
	<li><code>1 &lt;= f<sub>i</sub>, changeTime &lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= r<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= numLaps &lt;= 1000</code></li>
</ul>

from math import inf
from typing import List

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        # Step 1: Precompute the minimum lap times for consecutive laps with a single tire
        min_time_for_consecutive_laps = []
        cumulative_time_per_tire = [0] * len(tires)

        while True:
            for i, (initial_time, degradation_factor) in enumerate(tires):
                cumulative_time_per_tire[i] += initial_time
                initial_time *= degradation_factor
                tires[i][0] = initial_time

            min_time_next_lap = min(cumulative_time_per_tire)
            min_time_for_consecutive_laps.append(min_time_next_lap)

            if min_time_next_lap > changeTime + min_time_for_consecutive_laps[0]:
                break

        # Step 2: Use DP to find the minimum time to complete all laps
        dp = [inf] * numLaps  # Initialize DP array with infinite times

        for currentLap in range(numLaps):
            for consecutiveLapsIndex in range(len(min_time_for_consecutive_laps)):
                consecutiveLaps = consecutiveLapsIndex + 1

                if currentLap < consecutiveLaps:
                    # If the current number of laps is fewer than the number of consecutive laps, use the precomputed time directly
                    dp[currentLap] = min(dp[currentLap], min_time_for_consecutive_laps[consecutiveLapsIndex])
                    break
                else:
                    # Compute time using consecutiveLaps and add the optimal time for the remaining laps after a tire change
                    remainingLaps = currentLap - consecutiveLaps
                    dp[currentLap] = min(dp[currentLap], min_time_for_consecutive_laps[consecutiveLapsIndex] + dp[remainingLaps] + changeTime)

                    # Detailed Example and Explanation:
                    # Consider dp[currentLap] for currentLap = 3:
                    # dp[3] = min(dp[3], min_time_for_consecutive_laps[1] + dp[3 - 2] + changeTime)
                    # dp[3] = min(dp[3], 8 + dp[1] + 5)
                    # dp[1] is the time for 2 laps which is already computed as 7
                    # Therefore, dp[3] = min(dp[3], 8 + 7 + 5) = 20 (if dp[3] was initially infinite)

                    # Diagram:
                    # Lap 1: 2 seconds with tire 0
                    # Lap 2: 7 seconds with tire 0
                    # Lap 3: Change tire (5 seconds) and continue 1 more lap
                    # Total: 2 + 7 + 5 + 7 = 21 seconds

                    # Explanation of 'consecutiveLaps' and 'remainingLaps':
                    # 'consecutiveLaps': This represents the number of consecutive laps using the same tire
                    # 'remainingLaps': The laps remaining after completing 'consecutiveLaps' laps
                    
                    # Consider we have numLaps = 4 and min_time_for_consecutive_laps = [2, 7]
                    # dp[0] = min(dp[0], 2)
                    # dp[1] = min(dp[1], 7)
                    # dp[2] = min(dp[2], 2 + 7 + 5)
                    # dp[3] = min(dp[3], 2 + 7 + 5 + 7)
                    # Iterations:
                    # currentLap 0 -> 1st lap, dp[0] = 2
                    # currentLap 1 -> 2nd lap, dp[1] = 7
                    # currentLap 2 -> 3rd lap, dp[2] = 14
                    # currentLap 3 -> 4th lap, dp[3] = 21

        return dp[-1]

# Example usage:
sol = Solution()
print(sol.minimumFinishTime([[2, 3], [3, 4]], 5, 4))  # Output: 21

2423