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
Recognizing 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. For each day, it considers buying a 1-day, 7-day, or 30-day ticket and uses binary search or linear scan to find the next day not covered by that ticket. This reduces redundant calculations by reusing previously computed results stored in a dp array.
Optimal Approach
Use 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. For each day, compute the cost of buying each ticket type plus dp at the index of the next uncovered day. The answer is dp[0]. This approach runs in O(n) time with O(n) space.
Time
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
| 6 | for i in range(n - 1, -1, -1): |
| 8 | cost1 = costs[0] + dp[i + 1] |
| 10 | j = i |
| 11 | while j < n and days[j] < days[i] + 7: |
| 12 | j += 1 |
| 13 | cost7 = costs[1] + dp[j] |
| 15 | j = i |
| 16 | while j < n and days[j] < days[i] + 30: |
| 17 | j += 1 |
| 18 | cost30 = costs[2] + dp[j] |
| 20 | dp[i] = min(cost1, cost7, cost30) |
Objective
To compute the minimal cost for each travel day by considering all ticket options and leveraging dp for future costs.
Key Insight
Iterating backward ensures that when computing dp[i], all dp[j] for j > i are already computed. For each ticket type, the algorithm finds the next index j where the ticket coverage ends, then adds the ticket cost to dp[j]. Taking the minimum among all ticket options yields dp[i]. This approach exploits the problem's optimal substructure and overlapping subproblems.
Interview Quick-Check
Core Logic
For each day i, calculate the cost of buying each ticket type plus the minimal cost from the next uncovered day, then select the minimum.
Common Pitfalls & Bugs
Failing to correctly find the next uncovered day index after ticket coverage leads to incorrect dp values and suboptimal solutions.
Complexity
The inner while loops advance indices forward without revisiting, ensuring O(n) total time complexity.
Return the Minimal Cost to Cover All Travel Days
| 22 | return dp[0] |
Objective
To output the minimal cost required to cover all travel days starting from the first day.
Key Insight
dp[0] holds the minimal cost to cover all travel days from the start, computed by considering all ticket options and their coverage. Returning dp[0] provides the final answer to the problem.
Interview Quick-Check
Core Logic
Returning dp[0] gives the minimal cost to cover all travel days starting from the first day.
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.
cost1 = costs[0] + dp[i + 1]Calculate cost of buying a 1-day ticket plus dp for the next day.
A 1-day ticket covers only the current day, so the cost is the ticket price plus the minimal cost starting from the next day, dp[i+1].
cost7 = costs[1] + dp[j]Calculate cost of buying a 7-day ticket plus dp at index j.
The 7-day ticket cost plus the minimal cost from the first uncovered day after coverage yields the total cost for this option.
cost30 = costs[2] + dp[j]Calculate cost of buying a 30-day ticket plus dp at index j.
The 30-day ticket cost plus the minimal cost from the first uncovered day after coverage yields the total cost for this option.
dp = [0] * (n + 1)Initialize the dp array with zeros, length n+1.
This array stores the minimal cost to cover travel days from each index to the end, with dp[n] = 0 as the base case representing no remaining days.
for i in range(n - 1, -1, -1):Iterate backward through the travel days from last to first.
Backward iteration ensures that when computing dp[i], all dp[j] for j > i are already computed, enabling bottom-up dynamic programming.
return dp[0]Return the minimal cost to cover all travel days starting from the first day.
dp[0] contains the minimal total cost to cover all travel days, computed by considering all ticket options and their coverage.
j += 1Increment j to move to the next day.
Incrementing j progresses the search for the next uncovered day after the 7-day ticket coverage.
j += 1Increment j to move to the next day.
Incrementing j progresses the search for the next uncovered day after the 30-day ticket coverage.
j = iInitialize index j to current day index i for 7-day ticket coverage calculation.
Starting j at i allows scanning forward to find the first day not covered by the 7-day ticket starting at days[i].
j = iInitialize index j to current day index i for 30-day ticket coverage calculation.
Starting j at i allows scanning forward to find the first day not covered by the 30-day ticket starting at days[i].
n = len(days)Calculate the number of travel days.
Knowing the total number of travel days allows the algorithm to size the dp array and control iteration boundaries.
Test Your Understanding
Why does the algorithm jump to the next uncovered day index after buying a ticket instead of checking every subsequent day?
Because each ticket covers a continuous range of days, the cost after buying a ticket depends only on the minimal cost starting from the first day not covered by that ticket. Jumping directly to that index avoids redundant calculations and leverages the optimal substructure captured in dp.
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