题目分析

本题要求在 numLaps 圈赛道中，通过选择合适的轮胎和换胎策略，使得总耗时最小。每个轮胎 [fi, ri] 连续使用时，第 x 圈的耗时为 fi * ri^(x-1)，换胎需要固定时间 changeTime。

关键难点在于：直接枚举所有轮胎和圈数会超时（numLaps 最大 1000，但轮胎数量可观）。我们需要挖掘一个核心性质来压缩状态空间。

---

核心优化思路：连续使用同一个轮胎的圈数有限

如果一直用同一个轮胎跑下去，单圈耗时 fi * ri^(x-1) 会随着指数增长。一旦某圈的耗时超过了换胎后从头跑一圈的总时间，继续使用该轮胎就比换胎更差了。

换胎后从头跑一圈的总时间是：changeTime + fi（换胎 + 新胎的第 1 圈）。所以当 fi * ri^(x-1) > changeTime + fi 时，继续跑就不划算了。

最极端情况取 fi = 1（最小）、ri = 2（最小比值），解不等式 2^(x-1) > changeTime + 1。根据题目数据范围 changeTime 可达 10^5，取 changeTime = 10^5 时，解得 x ≈ 17.6。因此连续使用同一个轮胎跑超过 17 圈一定不是最优方案。

这意味着：

· 我们可以只用最多 17 圈作为“块”来考虑
· 预处理出连续跑 j 圈（j ≤ 17）的最小耗时 min_sec[j]

---

算法步骤

1. 预处理 min_sec[]（连续跑 j 圈的最小耗时）

```python
min_sec = [inf] * 18  # 下标 0~17 有效
for f, r in tires:
    lap_time = f
    total_time = 0
    for j in range(1, 18):
        total_time += lap_time
        # 如果继续跑还不如换胎，提前剪枝
        if lap_time > changeTime + f:
            break
        min_sec[j] = min(min_sec[j], total_time)
        lap_time *= r  # 下一圈耗时
```

对于每种轮胎，计算连续跑 1、2、…… 圈的总耗时，并更新到 min_sec。

2. 动态规划

定义 dp[i] 表示跑完 i 圈的最少总时间。状态转移：考虑最后一段连续跑了 j 圈（不换胎），前面 i-j 圈已经最优，再加上 changeTime 完成换胎。

转移方程：

```
dp[i] = min{ dp[i-j] + min_sec[j] + changeTime }  (1 ≤ j ≤ min(17, i))
```

边界条件：dp[0] = 0（0 圈耗时 0）。需要注意的是，第一段连续跑不需要换胎，但为了方便统一处理，可以在初始化时将 dp[0] 设为 -changeTime，这样转移公式可以统一为 dp[i] = min(dp[i-j] + min_sec[j] + changeTime)。

最终答案为 dp[numLaps]。

---

Python 代码实现

```python
from typing import List

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        INF = 10**18
        
        # 预处理连续跑j圈的最小耗时（j ≤ 17）
        # 上界取 17 是因为随着圈数增加，耗时指数增长，超过 17 圈一定不如换胎
        min_sec = [INF] * 18
        min_sec[0] = 0  # 跑0圈耗时0
        
        for f, r in tires:
            lap_time = f
            total_time = 0
            for j in range(1, 18):
                total_time += lap_time
                # 如果继续跑还不如换胎，提前剪枝（注意：即使不满足也仍需继续，因为可能更优）
                min_sec[j] = min(min_sec[j], total_time)
                lap_time *= r
                # 如果下一圈耗时已经大于换胎后从头跑，可以提前跳出
                if lap_time > changeTime + f:
                    break
        
        # 动态规划
        dp = [INF] * (numLaps + 1)
        dp[0] = 0
        
        for i in range(1, numLaps + 1):
            # 枚举最后一段连续跑的圈数 j
            for j in range(1, min(17, i) + 1):
                if min_sec[j] < INF:  # 确保该圈数有可行的轮胎
                    dp[i] = min(dp[i], dp[i - j] + min_sec[j] + changeTime)
            # 如果 i == j（即全程不换胎的情况），第一种情况减去了多余的一次 changeTime，需要特判
            # 可以用初始化 dp[0] = -changeTime 的方法统一处理
        return dp[numLaps]
```

---

代码优化

上面的通用解法中，由于 dp[0] = 0，在 i == j 时转移会多加一个 changeTime。我们可以通过初始化 dp[0] = -changeTime 来统一处理，同时注意越界问题：

```python
from typing import List

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        INF = 10**18
        
        # 预处理连续跑j圈的最小耗时
        min_sec = [INF] * 18
        for f, r in tires:
            lap_time = f
            total_time = 0
            for j in range(1, 18):
                total_time += lap_time
                min_sec[j] = min(min_sec[j], total_time)
                lap_time *= r
                # 提前剪枝：下一圈耗时超过换胎后从头跑即可跳出（因为后续更大）
                if lap_time > changeTime + f:
                    break
        
        dp = [INF] * (numLaps + 1)
        dp[0] = -changeTime  # 巧妙处理：减少一次换胎操作
        
        for i in range(1, numLaps + 1):
            # 枚举最后一段连续跑的圈数
            for j in range(1, min(17, i) + 1):
                if min_sec[j] < INF:
                    dp[i] = min(dp[i], dp[i - j] + min_sec[j] + changeTime)
        
        return dp[numLaps]
```

---

复杂度分析

· 时间复杂度：O(numLaps * 17 + 轮胎数 * 17) ≈ O(1000 * 17 + 1e5 * 17)。
· 空间复杂度：O(numLaps)，主要存储 DP 数组。

---

关键点总结

1. 连续跑圈数上界：由于耗时指数增长，连续使用同一轮胎跑超过 17 圈一定不是最优解。
2. 预处理 min_sec[j]：求出所有轮胎中连续跑 j 圈的最小耗时。
3. DP 状态定义：dp[i] 表示跑完 i 圈的最少总时间。
4. DP 转移：最后一段连续跑 j 圈，加上前面的最优解和换胎时间。
5. 边界处理：dp[0] = -changeTime 或 dp[0] = 0 配合特判，合理消除第一次的换胎操作。