Minimum Time to Finish the Race LeetCode solution in Python

1
class Solution:
2
    def minimumFinishTime(
3
        self, tires: List[List[int]], changeTime: int, numLaps: int
4
    ) -> int:
5
        # by observation, we can try to find out the optimal usage within certain numLaps
6
        # use DP
7
        # the optimal usage of this lap = min(change tire , no change)
8
        # dp(laps) = min( dp(laps-1)+dp(1) + dp(laps-2)+dp(2) + ...)
9

10
        # we don't want to use tires too many laps, which will create unrealistic single lap time
11
        # we can evaluate single lap time by using changeTime <= 100000 and r >= 2
12
        # x = minimal continously laps
13
        # single lap time = 1*2^x <= 100000 -> x can't go more than 19
14
        limit = 19
15
        tires = list(set([(t1, t2) for t1, t2 in tires]))
16
        memo = [
17
            [(-1, -1) for _ in range(min(limit, numLaps) + 1)]
18
            for _ in range(len(tires))
19
        ]
20

21
        for i in range(len(tires)):
22
            for j in range(1, min(limit, numLaps) + 1):  # lap 1 to numLaps
23
                if j == 1:
24
                    memo[i][j] = (tires[i][0], tires[i][0])  # total time, lap time
25
                else:
26
                    # print('i, j', i, j)
27
                    tmp = (
28
                        memo[i][j - 1][1] * tires[i][1]
29
                    )  # cost of continuously use tire this lap
30
                    memo[i][j] = (memo[i][j - 1][0] + tmp, tmp)
31

32
        @cache
33
        def dp(laps):
34
            if laps == 1:
35
                return min(memo[i][1][0] for i in range(len(tires)))
36

37
            # no change:
38
            best_time = (
39
                min(memo[i][laps][0] for i in range(len(tires)))
40
                if laps <= limit
41
                else float("inf")
42
            )
43

44
            # change tire:
45
            # e.g. change tire at this lap and see if it'll be faster -> dp(laps-1) + changeTime + dp(1)
46
            # check all previous laps: dp(a) + changeTime + dp(b) until a < b
47
            for j in range(1, laps):
48
                a, b = laps - j, j
49
                if a >= b:
50
                    ta = dp(a)
51
                    tb = dp(b)
52
                    if ta + tb + changeTime < best_time:
53
                        best_time = ta + tb + changeTime
54
            return best_time
55

56
        return dp(numLaps)