Minimum Cost For Tickets: Dynamic Programming on a Calendar

You are planning a year of train travel. You know exactly which days you will travel, and you can buy three kinds of passes: a 1-day pass, a 7-day pass, or a 30-day pass. Each pass covers consecutive days starting from the day you use it. What is the cheapest way to cover every travel day?

This is LeetCode 983: Minimum Cost For Tickets, and it is a beautiful example of dynamic programming on a calendar. Instead of iterating over items or positions in an array, you iterate over days. The core DP idea is the same as Coin Change, but the framing feels different enough that it trips people up the first time they see it.

The problem

You are given a sorted list of days when you will travel (e.g., [1, 4, 6, 7, 8, 20]) and an array costs of length 3, where costs[0] is the price of a 1-day pass, costs[1] is the price of a 7-day pass, and costs[2] is the price of a 30-day pass. Return the minimum cost to cover every travel day.

The trick is that buying a 7-day pass on day 4 covers days 4 through 10, which handles four travel days (4, 6, 7, 8) in one purchase. A 30-day pass covers even more. The question is finding the right combination.

The brute force approach

The most direct approach is to try every possible ticket at every travel day and recurse. At each travel day, you branch three ways: buy a 1-day pass, buy a 7-day pass, or buy a 30-day pass. Then you skip ahead past the days covered by that pass and solve the remaining days recursively.

def mincostTickets(days, costs):
    def helper(i):
        if i >= len(days):
            return 0

        # 1-day pass: covers only days[i]
        one = costs[0] + helper(i + 1)

        # 7-day pass: skip all days within 7 days of days[i]
        j = i
        while j < len(days) and days[j] < days[i] + 7:
            j += 1
        seven = costs[1] + helper(j)

        # 30-day pass: skip all days within 30 days of days[i]
        k = i
        while k < len(days) and days[k] < days[i] + 30:
            k += 1
        thirty = costs[2] + helper(k)

        return min(one, seven, thirty)

    return helper(0)

This works but it is exponential. Each travel day branches into three choices, and the recursion tree grows fast. With up to 365 travel days, this will not finish in time.

The key insight

The state is dp[i] = minimum cost to cover all travel through day i. For non-travel days, dp[i] = dp[i-1] because you do not need a ticket. For travel days, you pick the best of three options:

• Buy a 1-day pass today: dp[i-1] + costs[0]
• Buy a 7-day pass that covers today: dp[max(0, i-7)] + costs[1]
• Buy a 30-day pass that covers today: dp[max(0, i-30)] + costs[2]

The max(0, i-7) handles the case where looking back 7 days would go before day 0. If a 7-day pass on day 3 covers days 3 through 9, then the cost before that pass is dp[max(0, 3-7)] = dp[0] = 0.

Step-by-step walkthrough

Let's trace through days = [1, 4, 6, 7, 8, 20] with costs = [2, 7, 15]:

Notice the pattern: non-travel days just carry the previous cost forward. Travel days compare all three ticket options and keep the minimum. The 7-day pass wins at day 7 because it is cheaper than stacking individual 1-day passes. But by day 20, the gap between day 8 and day 20 is so large that buying individual passes is cheaper than a 30-day pass.

The code

def mincostTickets(self, days, costs):
    travel = set(days)
    last = days[-1]
    dp = [0] * (last + 1)

    for i in range(1, last + 1):
        if i not in travel:
            dp[i] = dp[i - 1]
        else:
            dp[i] = min(
                dp[i - 1] + costs[0],
                dp[max(0, i - 7)] + costs[1],
                dp[max(0, i - 30)] + costs[2]
            )

    return dp[last]

The code is clean and follows the DP recurrence directly. You convert days to a set for O(1) lookup, then sweep from day 1 to the last travel day. On non-travel days, copy the previous value. On travel days, compare three ticket options and keep the minimum.

Complexity analysis

Where n is the number of travel days and last_day is the value of the last travel day (at most 365 per the problem constraints). The DP approach is O(365) in the worst case, which is effectively constant time.

The building blocks

Linear DP with variable lookback

This problem uses the same fundamental pattern as Coin Change. In Coin Change, you iterate over amounts and for each amount you look back by each coin denomination. Here, you iterate over days and look back by each ticket duration (1, 7, 30). The structure is identical:

• State: dp[i] = optimal cost through position i
• Transition: try each "jump" size and pick the best
• Base case: dp[0] = 0

The only twist is the non-travel day shortcut: dp[i] = dp[i-1] when no ticket is needed. This makes the DP sparse in a sense. You only do real work on travel days, and non-travel days are free passes.

The calendar DP pattern

Some DP problems iterate over an array index. Others iterate over a value range (like amounts in Coin Change). This problem iterates over calendar days. The calendar framing shows up in scheduling problems, interval problems, and anywhere you have events spread across a timeline.

The key realization is that calendar days are just another axis to iterate over. If you can do DP over array indices, you can do DP over dates. The mechanics are the same.

Edge cases

• Single travel day: e.g., days = [5], costs = [2, 7, 15]. The answer is min(2, 7, 15) = 2. Always check that you are not overpaying with a longer pass for just one day.
• All days are travel days: e.g., days = [1, 2, 3, ..., 30]. A single 30-day pass might beat 30 individual 1-day passes. Compare 30 * costs[0] vs costs[2].
• Gaps between travel clusters: e.g., days = [1, 2, 3, 100, 101, 102]. The gap means a 30-day pass cannot cover both clusters. You effectively solve two independent subproblems.
• 7-day pass is cheaper than 7 individual 1-day passes: this is the common case where the 7-day pass shines. If costs[1] is less than 7 * costs[0], clusters of consecutive days benefit from it.
• 30-day pass is very cheap: if costs[2] is less than costs[0], then a 30-day pass is always optimal. The DP handles this naturally.
• Only one travel day per month: the 1-day pass is almost certainly cheapest. The 7-day and 30-day passes waste money covering empty days.

From understanding to recall

You can follow the DP table trace above, and the recurrence probably makes sense right now. But will you be able to write this from scratch in a week? The tricky part is not the logic. It is remembering the setup: iterate over calendar days, skip non-travel days, and use max(0, i-duration) for the lookback.

Spaced repetition is how you bridge the gap between understanding and recall. You revisit this problem at increasing intervals, write the recurrence from memory, and after a few reps the calendar DP pattern becomes automatic. When you see a scheduling or timeline problem in an interview, your brain will jump to "iterate over days, try ticket options at each travel day" without hesitation.

The calendar DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Coin Change - The classic unbounded knapsack DP, same "try each option and take the best" structure with coin denominations instead of ticket durations
• Climbing Stairs - The simplest linear DP problem, a good starting point before tackling calendar-based DP
• House Robber - Another linear DP where you make a decision at each step (rob or skip), showing the same "pick the best option" pattern