983. Minimum Cost For Tickets

Problem¶

Given sorted travel days and prices for 1-, 7-, and 30-day passes, find the minimum cost to cover every travel day.

Example: days = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15] → 11 (a 1-day pass, a 7-day pass, and another 1-day pass).

Key trick¶

Let dp[d] be the minimum cost to cover all travel through day d. On a travel day, compare passes ending on that day; on any other day, carry the cost forward.

Trap¶

A 7-day pass covers its purchase day and the next six days. Also, non-travel days still need DP entries so pass boundaries work correctly.

Why is it interesting?¶

Buying a longer pass can be optimal even when it starts before the next travel day. The DP avoids having to decide the exact purchase date in advance.

Python solution¶

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

        for d in range(1, len(dp)):
            if d not in travel:
                dp[d] = dp[d - 1]
                continue

            # Each option covers d and looks back past that pass's duration.
            dp[d] = min(
                dp[d - 1] + costs[0],
                dp[max(0, d - 7)] + costs[1],
                dp[max(0, d - 30)] + costs[2],
            )

        return dp[-1]

Time: \(O(D + n)\). Space: \(O(D + n)\), where \(D\) is the last travel day and \(n\) is the number of travel days.

Comment on my solution¶

Your backward-DP idea is sound: define a state for the next uncovered travel day, then try each pass. The missing step is to compare all three pass choices at each state; making costs the outer loop does not do that naturally.

# Ideas:
# - look like knapsack DP
# - as buying tickets project you forward (to next time you need to buy)
#   - maybe we could run DP backward on days
#   - dp[i] = min cost to travel from day i to the end
# - loop on costs is the outer loop and we go forward
# - I don't see how to solve this


class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int: