Minimum Time to Finish the Race solution and explanation

def minTimeToFinishRace(tires, changeTime, numLaps):
    max_laps = 20
    min_time_for_laps = [float('inf')] * (max_laps + 1)

    for f, r in tires:
        curr_time = 0
        curr_factor = 1
        for lap in range(1, max_laps + 1):
            curr_time += f * curr_factor
            if curr_time > changeTime + f:
                break
            min_time_for_laps[lap] = min(min_time_for_laps[lap], curr_time)
            curr_factor *= r

    dp = [float('inf')] * (numLaps + 1)
    dp[0] = 0
    for laps in range(1, numLaps + 1):
        for k in range(1, min(laps, max_laps) + 1):
            dp[laps] = min(dp[laps], dp[laps - k] + min_time_for_laps[k] + (0 if laps == k else changeTime))

    return dp[numLaps]

public class Solution {
    public int minTimeToFinishRace(int[][] tires, int changeTime, int numLaps) {
        int maxLaps = 20;
        int[] minTimeForLaps = new int[maxLaps + 1];
        Arrays.fill(minTimeForLaps, Integer.MAX_VALUE);

        for (int[] tire : tires) {
            int f = tire[0], r = tire[1];
            int currentTime = 0, currentFactor = 1;
            for (int lap = 1; lap <= maxLaps; lap++) {
                currentTime += f * currentFactor;
                if (currentTime > changeTime + f) break;
                minTimeForLaps[lap] = Math.min(minTimeForLaps[lap], currentTime);
                currentFactor *= r;
            }
        }

        int[] dp = new int[numLaps + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int laps = 1; laps <= numLaps; laps++) {
            for (int k = 1; k <= Math.min(laps, maxLaps); k++) {
                dp[laps] = Math.min(dp[laps], dp[laps - k] + minTimeForLaps[k] + (laps == k ? 0 : changeTime));
            }
        }

        return dp[numLaps];
    }
}

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minTimeToFinishRace(vector<vector<int>>& tires, int changeTime, int numLaps) {
    int maxLaps = 20;
    vector<int> minTimeForLaps(maxLaps + 1, INT_MAX);

    for (auto& tire : tires) {
        int f = tire[0], r = tire[1];
        int currentTime = 0, currentFactor = 1;
        for (int lap = 1; lap <= maxLaps; lap++) {
            currentTime += f * currentFactor;
            if (currentTime > changeTime + f) break;
            minTimeForLaps[lap] = min(minTimeForLaps[lap], currentTime);
            currentFactor *= r;
        }
    }

    vector<int> dp(numLaps + 1, INT_MAX);
    dp[0] = 0;
    for (int laps = 1; laps <= numLaps; laps++) {
        for (int k = 1; k <= min(laps, maxLaps); k++) {
            dp[laps] = min(dp[laps], dp[laps - k] + minTimeForLaps[k] + (laps == k ? 0 : changeTime));
        }
    }

    return dp[numLaps];
}

function minTimeToFinishRace(tires, changeTime, numLaps) {
    const maxLaps = 20;
    const minTimeForLaps = new Array(maxLaps + 1).fill(Infinity);

    for (const [f, r] of tires) {
        let currentTime = 0, currentFactor = 1;
        for (let lap = 1; lap <= maxLaps; lap++) {
            currentTime += f * currentFactor;
            if (currentTime > changeTime + f) break;
            minTimeForLaps[lap] = Math.min(minTimeForLaps[lap], currentTime);
            currentFactor *= r;
        }
    }

    const dp = new Array(numLaps + 1).fill(Infinity);
    dp[0] = 0;
    for (let laps = 1; laps <= numLaps; laps++) {
        for (let k = 1; k <= Math.min(laps, maxLaps); k++) {
            dp[laps] = Math.min(dp[laps], dp[laps - k] + minTimeForLaps[k] + (laps === k ? 0 : changeTime));
        }
    }

    return dp[numLaps];
}

function minimumFinishTime(tires: number[][], changeTime: number, numLaps: number): number {
    const cost: number[] = Array(18).fill(Infinity);
    for (const [f, r] of tires) {
        let s = 0;
        let t = f;
        for (let i = 1; t <= changeTime + f; ++i) {
            s += t;
            cost[i] = Math.min(cost[i], s);
            t *= r;
        }
    }
    const f: number[] = Array(numLaps + 1).fill(Infinity);
    f[0] = -changeTime;
    for (let i = 1; i <= numLaps; ++i) {
        for (let j = 1; j < Math.min(18, i + 1); ++j) {
            f[i] = Math.min(f[i], f[i - j] + cost[j]);
        }
        f[i] += changeTime;
    }
    return f[numLaps];
}

func minimumFinishTime(tires [][]int, changeTime int, numLaps int) int {
	const inf = 1 << 30
	cost := [18]int{}
	for i := range cost {
		cost[i] = inf
	}
	for _, e := range tires {
		f, r := e[0], e[1]
		s, t := 0, f
		for i := 1; t <= changeTime+f; i++ {
			s += t
			cost[i] = min(cost[i], s)
			t *= r
		}
	}
	f := make([]int, numLaps+1)
	for i := range f {
		f[i] = inf
	}
	f[0] = -changeTime
	for i := 1; i <= numLaps; i++ {
		for j := 1; j < min(18, i+1); j++ {
			f[i] = min(f[i], f[i-j]+cost[j])
		}
		f[i] += changeTime
	}
	return f[numLaps]
}