Minimum Skips to Arrive at Meeting On Time: DP on Skips

You are given an array dist where dist[i] is the length of the i-th road, an integer speed, and an integer hoursBefore. You travel along n roads sequentially. After finishing each road (except the last), you must wait until the next integer hour before continuing, unless you choose to skip the rest. Return the minimum number of skips needed to arrive at the meeting on time, or -1 if it is impossible.

This is LeetCode 1883: Minimum Skips to Arrive at Meeting On Time, a hard DP problem where the key challenge is deciding which rest stops to skip. The brute force tries all combinations, but DP on the skip count collapses the exponential search into a clean O(n^2) solution.

Why this problem matters

This problem teaches a pattern that appears whenever you have a limited number of "exceptions" you can use along a sequence. Instead of tracking which specific positions you skip, you track how many skips you have used so far and what the best outcome is for each count. This "DP on exception count" pattern shows up in problems like Best Time to Buy and Sell Stock with at most k transactions, or any scenario where you have a budget of special moves.

The resting mechanic (ceiling to the next integer hour) also teaches you to be careful with floating point. Multiplying everything by speed to stay in integers is a technique worth having in your toolkit.

The brute force approach

The most direct approach is to try every possible subset of rest stops to skip. With n - 1 rest stops, there are 2^(n-1) subsets.

def minSkips_brute(dist, speed, hoursBefore):
    n = len(dist)
    best = n

    def backtrack(i, time, skips):
        nonlocal best
        if i == n:
            if time <= hoursBefore * speed:
                best = min(best, skips)
            return
        t = time + dist[i]
        if i < n - 1:
            rest_time = ((t + speed - 1) // speed) * speed
            backtrack(i + 1, rest_time, skips)
            backtrack(i + 1, t, skips + 1)
        else:
            backtrack(i + 1, t, skips)

    backtrack(0, 0, 0)
    return best if best < n else -1

This is O(2^n) time, which is far too slow for n up to 1000. But it reveals the structure: at each rest stop, you make a binary choice (rest or skip), and the total time depends on the sequence of choices. That binary choice at each step is exactly what DP can optimize.

The key insight

Define dp[i][j] as the minimum total travel time (in speed-units, to avoid fractions) after completing road i using exactly j skips. For each road, you have two transitions:

1. Rest (no skip): take dp[i-1][j], add dist[i-1], then round up to the next multiple of speed. This costs 0 skips.
2. Skip: take dp[i-1][j-1], add dist[i-1], and do not round up. This costs 1 skip.

For the last road, you never need to rest (there is no waiting after the final road), so you just add the distance directly.

Walking through it step by step

Let's trace through dist = [1, 3, 2], speed = 4, hoursBefore = 2. The deadline in speed-units is 2 * 4 = 8. We build the DP table row by row.

The answer is 1. With zero skips, you arrive at time 10 (in speed-units), which exceeds the deadline of 8. With one skip (skipping the rest after road 1), you arrive at time 6, which is within the deadline.

The complete solution

def minSkips(dist, speed, hoursBefore):
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i in range(1, n + 1):
        for j in range(i + 1):
            if dp[i - 1][j] < INF:
                t = dp[i - 1][j] + dist[i - 1]
                if i < n:
                    rest = ((t + speed - 1) // speed) * speed
                else:
                    rest = t
                dp[i][j] = min(dp[i][j], rest)
            if j > 0 and dp[i - 1][j - 1] < INF:
                t = dp[i - 1][j - 1] + dist[i - 1]
                dp[i][j] = min(dp[i][j], t)

    for j in range(n + 1):
        if dp[n][j] <= hoursBefore * speed:
            return j
    return -1

Here is what each piece does:

1. Initialize dp[0][0] = 0. Before any road, zero time has elapsed and zero skips have been used.
2. For each road i (1 through n), for each possible skip count j (0 through i):
   • Rest transition: from dp[i-1][j], add dist[i-1], then ceil to the next multiple of speed (unless it is the last road). Update dp[i][j].
   • Skip transition: from dp[i-1][j-1], add dist[i-1] without ceiling. Update dp[i][j].
3. Find the answer: scan dp[n][0], dp[n][1], ... and return the first j where dp[n][j] is at most hoursBefore * speed.
4. Return -1 if no skip count is sufficient.

Complexity analysis

You can optimize space to O(n) by using a single row and updating it in reverse order (right to left on j), since each dp[i][j] only depends on dp[i-1][j] and dp[i-1][j-1].

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. DP on exception count

When you can use a limited number of "special moves" along a sequence, add the move count as a DP dimension. The state becomes dp[position][moves_used], and each transition either uses a move or does not.

dp = [[INF] * (max_moves + 1) for _ in range(n + 1)]
dp[0][0] = base_value

for i in range(1, n + 1):
    for j in range(i + 1):
        dp[i][j] = transition_normal(dp[i - 1][j], data[i - 1])
        if j > 0:
            dp[i][j] = min(dp[i][j], transition_special(dp[i - 1][j - 1], data[i - 1]))

This same skeleton solves "Best Time to Buy and Sell Stock with k transactions," "minimum cost with at most k modifications," and many other bounded-exception problems.

2. Integer arithmetic to avoid floating point

When the problem involves division and ceiling operations, multiply all quantities by the divisor so every value stays as an integer. This eliminates precision bugs.

time_in_units = time_raw * speed
deadline_in_units = hours * speed
rounded_up = ((time_in_units + speed - 1) // speed) * speed

This technique is essential in any problem where you compare fractional times or costs to a threshold.

Edge cases

Before submitting, make sure your solution handles these:

• All distances fit without any skips: if the total time with all rests is already within the deadline, the answer is 0.
• Impossible even with all skips: if sum(dist) / speed exceeds hoursBefore, return -1. No amount of skipping can help since skipping only removes wait time, not travel time.
• Single road (n = 1): there is no rest stop to skip. Either you arrive in time or you do not. The answer is 0 or -1.
• Speed equals 1: every road takes exactly dist[i] hours, and resting always rounds up to the next integer. The ceiling operation simplifies since dist[i] is already an integer.
• Large values: n up to 1000 with distances up to 10^5 and speed up to 10^6. The DP values can get large, so use integers (not floats) to avoid precision loss.
• Exact deadline match: dp[n][j] equals hoursBefore * speed exactly. This should return j since arriving exactly on time counts as on time.

Common mistakes

1. Using floating-point division. Computing time / speed as a float and then applying math.ceil leads to precision errors. For example, math.ceil(7.0 / 3.0) might give unexpected results due to floating-point rounding. Multiplying by speed and working in integers avoids this entirely.

2. Resting after the last road. The problem says you rest after each road except the last. If you apply the ceiling operation after the final road, you add unnecessary wait time and get a wrong answer.

3. Forgetting to check dp[i-1][j-1] < INF before the skip transition. If dp[i-1][j-1] is infinity (unreachable state), adding dist[i-1] to it is meaningless. Always guard against processing unreachable states.

4. Scanning for the answer in the wrong row. The answer is in row n (after all roads are completed), not row n-1. If you use 0-indexed roads, make sure you scan dp[n], not dp[n-1].

From understanding to recall

You have traced through the DP table, seen how rest and skip transitions fill in the values, and understood why integer arithmetic matters. But can you set up the state definition, write the two transitions, and handle the last-road special case from scratch in 15 minutes?

The details matter: initializing dp[0][0] = 0 with everything else as infinity, iterating j from 0 to i (not to n), applying the ceiling only for non-final roads, and scanning the last row for the smallest valid j. These are easy to mix up under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You write the DP setup, the rest-vs-skip transitions, and the answer scan from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "minimize skips" and the two-transition DP structure flows out without hesitation.

The DP on exception count pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Edit Distance - Another 2D DP problem where one dimension tracks the position and the other tracks the cost of operations
• Coin Change - Classic DP with optimization count, finding the minimum number of coins (analogous to minimum skips)
• Dungeon Game - DP with careful boundary handling and the importance of integer arithmetic over floating point

CodeBricks breaks the minimum skips problem into its DP-on-exception-count and integer-arithmetic building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a bounded-exception DP question shows up in your interview, you do not think about it. You just write it.