How does dynamic programming help in this problem?

Dynamic programming helps by breaking down the problem into smaller subproblems, tracking the minimum time to finish the race with each tire choice and lap. This allows for efficient computation without redundant recalculations.

What is the impact of tire swaps on the total time?

Tire swaps add a fixed change time, but they can result in significant savings if a tire's efficiency decreases after several laps. Minimizing unnecessary swaps is key to optimizing the total time.

How do I handle the exponential increase in lap times?

The exponential increase in lap times with each tire requires careful tracking of when to stop using a tire. You must weigh the benefits of switching tires against the added change time and the diminishing returns from using a tire for too long.

What are the edge cases I should consider for this problem?

Consider cases where only one tire type is available, where the change time is very high, or where there are very few laps. These edge cases will test the efficiency and correctness of your solution.

Can this problem be solved without dynamic programming?

While a brute force approach could work, dynamic programming provides a much more efficient way to solve this problem by storing intermediate results and avoiding redundant calculations.

#2188

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

完成比赛的最少时间

给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [f i , r i ] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 f i * r i (x-1) 秒。比方说，如果 f i = 3 且 r i = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 …

数组动态规划

题目描述

给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [f_i, r_i] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 f_i * r_i^(x-1) 秒。

比方说，如果 f_i = 3 且 r_i = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 = 6 秒，完成第 3 圈耗时 3 * 2² = 12 秒，依次类推。

同时给你一个整数 changeTime 和一个整数 numLaps 。

比赛总共包含 numLaps 圈，你可以选择任意一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 changeTime 秒换成任意一种轮胎（也可以换成当前种类的新轮胎）。

请你返回完成比赛需要耗费的最少时间。

示例 1：

输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
输出：21
解释：
第 1 圈：使用轮胎 0 ，耗时 2 秒。
第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
完成比赛的最少时间为 21 秒。

示例 2：

输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
输出：25
解释：
第 1 圈：使用轮胎 1 ，耗时 2 秒。
第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。
总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
完成比赛的最少时间为 25 秒。

提示：

1 <= tires.length <= 10⁵
tires[i].length == 2
1 <= f_i, changeTime <= 10⁵
2 <= r_i <= 10⁵
1 <= numLaps <= 1000

lightbulb

解题思路

方法一：预处理 + 动态规划

我们注意到，连续使用同一个轮胎 $(f, r)$ 跑 $i$ 圈，那么第 $i$ 圈的耗时不应该超过 $changeTime + f$ ，否则我们可以在第 $i$ 圈的时候换轮胎，这样总耗时会更少。即：

f \times r^{i-1} \leq changeTime + f

我们可以求出满足上式的最大的 $i$ ，要使得 $i$ 最大，那么 $f$ 和 $r$ 应该尽可能小，根据题目的数据范围，我们取 $f=1$ , $r=2$ ，那么 $2^{i-1} \leq changeTime + 1$ ，即 $i \leq \log_2(changeTime + 1) + 1$ 。根据这个结论，以及题目中 $changeTime$ 的数据范围，我们可以知道 $i$ 最大为 $17$ 。

我们定义 $cost[i]$ 表示使用同一个轮胎跑 $i$ 圈的最小耗时，那么我们可以预处理出 $cost$ 数组，然后使用动态规划求解即可。定义 $f[i]$ 表示跑 $i$ 圈的最小耗时，那么我们可以得到状态转移方程：

f[i] = (\min_{1 \leq j \leq \min(17, i)} f[i-j] + cost[j]) + changeTime

初始时 $f[0] = -changeTime$ ，最终答案为 $f[numLaps]$ 。

时间复杂度 $O((n + numLaps) \times \log T_{max})$ ，空间复杂度 $O(n + \log T_{max})$ ，其中 $T_{max}$ 是题目中 $f_i$ , $r_i$ 和 $changeTime$ 的最大值。本题中 $\log T_{max} \approx 17$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the ability to optimize state transitions using dynamic programming.
question_mark
Check if the candidate can handle exponential growth in lap times and tire changes effectively.
question_mark
Evaluate the candidate's approach to minimizing tire swaps and understanding the impact on time.

warning

常见陷阱

外企场景

error
Forgetting to account for the exponential increase in time for successive laps with each tire.
error
Improperly handling tire swaps, either by not considering them at all or by switching tires unnecessarily.
error
Overcomplicating the problem by trying to brute force all possible combinations instead of using dynamic programming.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Introduce additional tire types with different increase rates and see how the solution scales.
arrow_right_alt
Change the structure of the problem by limiting the number of tire swaps or changing the number of laps.
arrow_right_alt
Modify the problem to include constraints on when tire changes can occur, such as only changing after a set number of laps.

help

常见问题

外企场景

继续练习

#2172 数组的最大与和 #2163 删除元素后和的最小差值 #2218 从栈中取出 K 个硬币的最大面值和