Leetcode: 2188. Minimum Time to Finish the Race

Understand the problem

Given an array representing tires where \(tires[i] = [f_i, r_i]\), a cost to change tires and number of laps in the race. The time \(t\) for the tire \(i\) to make \(j\)th lap is \(t(i, j) = t(i, j - 1) + f_i \times r_i^j\). Determine the minimum times to finish the race.

Devise a plan

Can we simplify the problem while keeping it the same? As the cost of change tires is at most \(10^5\), we don't need to use a tire for more than 17 laps at most since \(r_i^17 \geq 2^17 \geq 10^5\).
Can we formulate the problem as a classical problem? Suppose that we have \(b[i]\) equal to the minimum time to make \(i\) laps with the same tire. Now, the problem is reduced to Knapsack problem. Time complexity is \(O(n \times m)\) with space \(O(n ^ 2)\).

Carry out the solution

class Solution:
    def minimumFinishTime(
        self, tires: List[List[int]], changeTime: int, numLaps: int
    ) -> int:
        N = len(tires)
        M = min(numLaps + 1, 17)
        best = [float("inf")] * M
        for i in range(N):
            cur = 0
            f, r = tires[i]
            p = 1
            for j in range(1, M):
                cur += f * p
                p *= r
                best[j] = min(best[j], cur)
                if cur > changeTime + f:
                    break

        @cache
        def dfs(i):
            if i == numLaps:
                return 0
            ans = float("inf")
            for j in range(1, min(M, numLaps - i + 1)):
                ans = min(ans, changeTime + best[j] + dfs(i + j))
            return ans

        return dfs(0) - changeTime