Hard

题目描述

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

  • 例如，如果 fi = 3 且 ri = 2，且该轮胎连续使用，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 = 6 秒，完成第 3 圈耗时 3 * 2^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^5
  • tires[i].length == 2
  • 1 <= fi, changeTime <= 10^5
  • 2 <= ri <= 10^5
  • 1 <= numLaps <= 1000

解题思路

这是一个动态规划问题，需要预处理和状态转移两个阶段。

核心思想：

  1. 预处理阶段：计算每种轮胎连续使用k圈的最小耗时，并找到全局最优
  2. 动态规划阶段：计算完成n圈的最小时间

关键观察：

  • 由于轮胎耗时呈指数增长（fi * ri^(x-1)），连续使用同一轮胎的圈数不会太多
  • 当连续使用超过某个阈值时，换轮胎会更优，这个阈值通常在20圈以内

算法步骤：

  1. 预处理：对于每个可能的连续圈数k（1到约20），计算所有轮胎中连续使用k圈的最小耗时minCost[k]

  2. 动态规划：定义dp[i]表示完成i圈的最小时间

    • 初始化：dp[0] = 0
    • 转移方程：dp[i] = min(dp[i], dp[i-k] + minCost[k])，其中k为连续使用的圈数
    • 注意：除了第一段，后续每段都需要加上换轮胎的时间changeTime

时间复杂度优化：

  • 预处理时，当轮胎耗时超过changeTime + minCost[1]时就停止计算，因为此时换轮胎更优
  • 这样可以将时间复杂度控制在合理范围内

这种方法巧妙地将复杂的轮胎选择问题转化为了经典的动态规划问题。

代码实现

class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        // 预处理：计算连续使用k圈的最小时间
        vector<int> minCost(20, INT_MAX);
        
        for (auto& tire : tires) {
            int f = tire[0], r = tire[1];
            int cost = 0, lapTime = f;
            
            for (int k = 1; k < 20 && lapTime <= changeTime + f; k++) {
                cost += lapTime;
                minCost[k] = min(minCost[k], cost);
                lapTime *= r;
            }
        }
        
        // 动态规划
        vector<int> dp(numLaps + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 1; i <= numLaps; i++) {
            for (int k = 1; k < 20 && k <= i; k++) {
                if (minCost[k] != INT_MAX) {
                    int prevCost = (i == k) ? 0 : dp[i - k] + changeTime;
                    if (prevCost != INT_MAX) {
                        dp[i] = min(dp[i], prevCost + minCost[k]);
                    }
                }
            }
        }
        
        return dp[numLaps];
    }
};

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        # 预处理：计算连续使用k圈的最小时间
        min_cost = [float('inf')] * 20
        
        for f, r in tires:
            cost = 0
            lap_time = f
            
            for k in range(1, 20):
                if lap_time > changeTime + f:
                    break
                cost += lap_time
                min_cost[k] = min(min_cost[k], cost)
                lap_time *= r
        
        # 动态规划
        dp = [float('inf')] * (numLaps + 1)
        dp[0] = 0
        
        for i in range(1, numLaps + 1):
            for k in range(1, min(20, i + 1)):
                if min_cost[k] != float('inf'):
                    prev_cost = 0 if i == k else dp[i - k] + changeTime
                    if prev_cost != float('inf'):
                        dp[i] = min(dp[i], prev_cost + min_cost[k])
        
        return dp[numLaps]

public class Solution {
    public int MinimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        // 预处理：计算连续使用k圈的最小时间
        int[] minCost = new int[20];
        Array.Fill(minCost, int.MaxValue);
        
        foreach (var tire in tires) {
            int f = tire[0], r = tire[1];
            long cost = 0, lapTime = f;
            
            for (int k = 1; k < 20 && lapTime <= changeTime + f; k++) {
                cost += lapTime;
                minCost[k] = (int)Math.Min(minCost[k], cost);
                lapTime *= r;
            }
        }
        
        // 动态规划
        int[] dp = new int[numLaps + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int i = 1; i <= numLaps; i++) {
            for (int k = 1; k < 20 && k <= i; k++) {
                if (minCost[k] != int.MaxValue) {
                    int prevCost = (i == k) ? 0 : dp[i - k] + changeTime;
                    if (prevCost != int.MaxValue) {
                        dp[i] = Math.Min(dp[i], prevCost + minCost[k]);
                    }
                }
            }
        }
        
        return dp[numLaps];
    }
}

var minimumFinishTime = function(tires, changeTime, numLaps) {
    const minTime = new Array(numLaps + 1).fill(Infinity);
    
    // For each tire, calculate minimum time to complete 1 to k consecutive laps
    const consecutive = new Array(numLaps + 1).fill(Infinity);
    
    for (let [f, r] of tires) {
        let time = 0;
        let lapTime = f;
        
        for (let laps = 1; laps <= numLaps && lapTime <= changeTime + f; laps++) {
            time += lapTime;
            consecutive[laps] = Math.min(consecutive[laps], time);
            lapTime *= r;
        }
    }
    
    minTime[0] = 0;
    
    for (let i = 1; i <= numLaps; i++) {
        for (let j = 1; j <= i; j++) {
            if (consecutive[j] !== Infinity) {
                let cost = consecutive[j];
                if (i > j) cost += changeTime;
                minTime[i] = Math.min(minTime[i], minTime[i - j] + cost);
            }
        }
    }
    
    return minTime[numLaps];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(T × 20 + N × 20)T为轮胎数量，N为圈数，20为连续使用的最大圈数
空间复杂度O(N + 20)dp数组和minCost数组的空间

相关题目