Minimum Cost For Tickets
Problem
Given an array days where each element is a day you will travel, and an array costs where costs[0], costs[1], and costs[2] represent the cost of a 1-day, 7-day, and 30-day ticket respectively, return the minimum cost needed to cover all travel days.
- 1 ≤ days.length ≤ 365
- 1 ≤ days[i] ≤ 365
- days is strictly increasing
- costs.length == 3
- 1 ≤ costs[i] ≤ 1000
Example
days = [1,4,6,7,8,20], costs = [2,7,15]11The algorithm considers each travel day starting from the last. For day 20, it calculates the cost of buying a 1-day ticket plus the cost for days after day 20 (which is zero), a 7-day ticket plus cost after day 20 (zero), and a 30-day ticket plus cost after day 20 (zero). It picks the minimum, which is 2. Moving backward, for day 8, it finds the next day not covered by a 7-day ticket starting at day 8 is day 20, so cost7 is 7 + dp at index of day 20. Similarly for 30-day tickets. By iterating backward and choosing the minimum among these options, the algorithm accumulates the minimal total cost. The critical moment is correctly identifying the next index after the coverage period for each ticket type, enabling the DP to build on previously computed results.
Approach
Straightforward Solution
A brute-force approach tries all combinations of tickets for each day, leading to exponential time complexity because of overlapping subproblems and repeated calculations.
Core Observation
The problem reduces to finding the minimum cost to cover all travel days, where each ticket covers a contiguous range of days starting from a chosen day. The cost for covering from day i depends on the cost of buying a ticket at day i plus the cost of covering the remaining days after the ticket expires.
Path to Optimal
PreviewRecognizing the overlapping subproblems and optimal substructure leads to a dynamic programming approach. By iterating backward through the travel days, the algorithm calculates the minimal cost to cover from each day to the end…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a bottom-up DP array dp of length n+1, where dp[i] represents the minimum cost to cover travel days from index i to the end. Iterate from the last travel day backward…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each travel day is processed once in a backward loop. The inner while loops advance indices forward without revisiting, resulting in an overall linear time complexity.
Space
O(n)
The dp array stores minimal costs for each of the n travel days plus one extra for the base case, resulting in O(n) auxiliary space.
Pattern Spotlight
Dynamic Programming (Interval Coverage)
When covering intervals with overlapping ranges and multiple coverage options, model the problem as a state machine over indices and use DP to accumulate minimal cost by jumping to the next uncovered index after each coverage choice.
Solution
| 1 | class Solution: |
| 2 | def mincostTickets(self, days, costs): |
| 3 | n = len(days) |
| 4 | dp = [0] * (n + 1) |
| 5 | |
| 6 | for i in range(n - 1, -1, -1): |
| 7 | |
| 8 | cost1 = costs[0] + dp[i + 1] |
| 9 | |
| 10 | j = i |
| 11 | while j < n and days[j] < days[i] + 7: |
| 12 | j += 1 |
| 13 | cost7 = costs[1] + dp[j] |
| 14 | |
| 15 | j = i |
| 16 | while j < n and days[j] < days[i] + 30: |
| 17 | j += 1 |
| 18 | cost30 = costs[2] + dp[j] |
| 19 | |
| 20 | dp[i] = min(cost1, cost7, cost30) |
| 21 | |
| 22 | return dp[0] |
Step-by-Step Solution
Initialize DP Array to Store Minimal Costs from Each Day
| 3 | n = len(days) |
| 4 | dp = [0] * (n + 1) |
Objective
To create a DP array that will hold the minimum cost to cover all travel days starting from each index.
Key Insight
By initializing dp with zeros and setting its length to n+1, the algorithm establishes a base case where dp[n] = 0, representing no cost beyond the last travel day. This setup enables bottom-up computation where each dp[i] depends on dp values at indices greater than i, ensuring all subproblems are solved before use.
Interview Quick-Check
Core Logic
The dp array stores the minimal cost to cover travel days from index i to the end, enabling reuse of previously computed results.
State & Boundaries
dp[n] = 0 represents the base case where no travel days remain to be covered.
Iterate Backwards Through Travel Days to Compute Minimal Costs
To compute the minimal cost for each travel day by considering all ticket options and leveraging dp for future costs.
Return the Minimal Cost to Cover All Travel Days
To output the minimal cost required to cover all travel days starting from the first day.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
dp[i] = min(cost1, cost7, cost30)Set dp[i] to the minimum of the three ticket cost options.
This min operation is the core DP logic that selects the optimal ticket choice at each step, embodying the principle of optimal substructure and enabling the bottom-up solution.
while j < n and days[j] < days[i] + 7:Advance j while days[j] is within 7 days of days[i].
This loop finds the first travel day beyond the 7-day coverage window, enabling the algorithm to jump directly to dp[j] for future cost calculation.
while j < n and days[j] < days[i] + 30:Advance j while days[j] is within 30 days of days[i].
This loop finds the first travel day beyond the 30-day coverage window, enabling the algorithm to jump directly to dp[j] for future cost calculation.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why does the algorithm jump to the next uncovered day index after buying a ticket instead of checking every subsequent day?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Minimum Cost For Tickets from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Minimum Cost For Tickets drill