# 2188. Minimum Time to Finish the Race
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-time-to-finish-the-race/description/
## 思路
根据题意定义```dp[i]```是跑```i```圈所需要的最短时间

所以我们需要计算跑i-j圈所需要的最少时间
于是我们遍历所有的```tire``` 对于每一个```tire```来说如果现在```跑一圈的时间-一开始跑一圈的时间f```比```changeTime```还要大 说明不换胎就已经不划算了 所以就不需要再往后计算了
这也是一个dp问题 那我们开多大的array去记录呢？
答案是20，在最极端的条件下，即```f=1```，```r=2```时，当x是第20圈的时候，跑一圈所花的时间就有```2^19=5e5```已经大于了```changeTime```的上限。所以无论对于什么轮胎，一次性跑20圈都是不划算的。
做到这里大体思路有了 但是会TLE 于是我们思考 如果两个tire A和B ```A.f<B.f``` ```A.r<B.r``` 那么是不是不需要考虑B呢 因此我们先排序来筛掉一些不可能用到的```tire```
## Code

class Solution {
public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
Arrays.sort(tires, (a,b)->(a[1]==b[1]?a[0]-b[0]:a[1]-b[1]));
List<int[]> newTires = new ArrayList<>();
for(int[] tire:tires){
if(newTires.size()>0 && newTires.get(newTires.size()-1)[0]<tire[0]) continue;
newTires.add(tire);
}
int[] minTime = new int[20];
Arrays.fill(minTime, Integer.MAX_VALUE/2);
minTime[0]=0;
for(int[] tire:newTires){
long currTime = tire[0];
int lap = 1;
while(currTime-tire[0]<=changeTime){
minTime[lap] = Math.min(minTime[lap], (int)currTime+minTime[lap-1]);
currTime *= tire[1];
lap++;
}
}
int[] dp = new int[numLaps+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i=1; i<=numLaps; i++){
for(int j=i-1; j>=0 && i-j<20; j--){
dp[i] = Math.min(dp[i], dp[j]+(j==0?0:changeTime)+minTime[i-j]);
}
}
return dp[numLaps];
}
}