LeetCode 983: Minimum Cost For Tickets

Problem Restatement

We are given two arrays:

days
costs

days contains the days of the year when we need to travel.

costs contains the prices of three ticket types:

A pass covers consecutive calendar days.

For example, if we buy a 7-day pass on day 3, it covers:

3, 4, 5, 6, 7, 8, 9

We need to return the minimum total cost needed to cover every travel day.

The official constraints are 1 <= days.length <= 365, 1 <= days[i] <= 365, days is strictly increasing, costs.length == 3, and 1 <= costs[i] <= 1000.

Input and Output

Function shape:

def mincostTickets(days: list[int], costs: list[int]) -> int:
    ...

Examples

Example 1:

days = [1, 4, 6, 7, 8, 20]
costs = [2, 7, 15]

One optimal plan is:

Total:

2 + 7 + 2 = 11

Answer:

11

Example 2:

days = [1,2,3,4,5,6,7,8,9,10,30,31]
costs = [2,7,15]

One optimal plan is:

Total:

15 + 2 = 17

Answer:

17

These match the official examples.

First Thought: Try Every Ticket Choice

At each uncovered travel day, we can buy one of three passes:

1-day pass
7-day pass
30-day pass

Then we skip all travel days covered by that pass and solve the remaining problem.

This gives a natural recursive solution.

For example, if the current travel day is days[i], and we buy a 7-day pass, it covers all travel days less than:

days[i] + 7

Then we continue from the first travel day not covered by that pass.

Without memoization, this repeats the same subproblems many times.

Key Insight

Define:

dp(i) = minimum cost to cover travel days from index i to the end

At index i, we try each ticket type.

If the pass duration is duration, then buying that pass costs:

cost + dp(next_index)

where next_index is the first index whose travel day is not covered by the pass.

The answer is:

dp(0)

Because days is strictly increasing, we can find next_index by moving forward or by binary search.

Algorithm

Use recursion with memoization.

For dfs(i):

1. If i == len(days), all travel days are covered, so return 0.
2. Try a 1-day pass.
3. Try a 7-day pass.
4. Try a 30-day pass.
5. For each pass, find the first travel day not covered.
6. Return the minimum cost among the three choices.

For a pass bought on days[i] with duration d, it covers days:

days[i], days[i] + 1, ..., days[i] + d - 1

So the first uncovered day must satisfy:

days[j] >= days[i] + d

Correctness

Let dfs(i) be the minimum cost to cover all travel days from index i onward.

If i == len(days), there are no remaining travel days, so the minimum cost is 0.

For any i < len(days), the travel day days[i] must be covered by some pass. In an optimal solution, consider the first pass that covers days[i]. That pass has duration either 1, 7, or 30.

If we choose a pass with duration d, it covers every travel day less than days[i] + d. The next remaining travel day is therefore the first index j such that:

days[j] >= days[i] + d

After buying that pass, the remaining optimal cost is exactly dfs(j).

The algorithm tries all three possible pass durations and takes the minimum. Therefore, it considers the first decision of every possible optimal plan.

By memoizing dfs(i), each subproblem is solved once. Since dfs(0) represents covering all travel days, the returned value is the minimum total cost.

Complexity

Let n = len(days).

Because n <= 365, this is easily fast enough.

Implementation

from functools import cache
from bisect import bisect_left

class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        durations = [1, 7, 30]
        n = len(days)

        @cache
        def dfs(i: int) -> int:
            if i == n:
                return 0

            best = float("inf")

            for duration, cost in zip(durations, costs):
                next_day = days[i] + duration
                j = bisect_left(days, next_day)
                best = min(best, cost + dfs(j))

            return best

        return dfs(0)

Code Explanation

We define the ticket durations:

durations = [1, 7, 30]

The recursive function means:

dfs(i)

minimum cost to cover travel days from days[i] onward.

If all travel days are already covered:

if i == n:
    return 0

For each ticket type:

for duration, cost in zip(durations, costs):

we compute the first calendar day not covered by the pass:

next_day = days[i] + duration

Then we find the first index with a travel day at least next_day:

j = bisect_left(days, next_day)

The total cost for this choice is:

cost + dfs(j)

We keep the cheapest choice:

best = min(best, cost + dfs(j))

Finally:

return dfs(0)

returns the minimum cost to cover all travel days.

Alternative Bottom-Up Implementation

Since the calendar has only 365 days, we can also use daily DP.

Let:

dp[day] = minimum cost to cover all travel days up to this calendar day

If day is not a travel day, the cost stays the same as yesterday.

If day is a travel day, choose the cheapest pass ending at this day.

class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        travel_days = set(days)
        last_day = days[-1]
        dp = [0] * (last_day + 1)

        for day in range(1, last_day + 1):
            if day not in travel_days:
                dp[day] = dp[day - 1]
            else:
                one_day = dp[max(0, day - 1)] + costs[0]
                seven_day = dp[max(0, day - 7)] + costs[1]
                thirty_day = dp[max(0, day - 30)] + costs[2]

                dp[day] = min(one_day, seven_day, thirty_day)

        return dp[last_day]

This version runs in O(365) time, which is constant under the given constraints.

Testing

def run_tests():
    s = Solution()

    assert s.mincostTickets([1, 4, 6, 7, 8, 20], [2, 7, 15]) == 11
    assert s.mincostTickets([1,2,3,4,5,6,7,8,9,10,30,31], [2, 7, 15]) == 17
    assert s.mincostTickets([1], [2, 7, 15]) == 2
    assert s.mincostTickets([1, 7, 30, 365], [3, 8, 20]) == 12
    assert s.mincostTickets([1, 2, 3, 4, 5, 6, 7], [3, 8, 20]) == 8

    print("all tests passed")

run_tests()