Minimum Cost for Tickets
Medium · Greedy · Array · Dynamic Programming
Problem
You have planned train trips on certain days of one year, given as the strictly increasing list days with values from 1 to 365.
Passes come in three kinds, priced by costs:
- a 1-day pass for costs[0],
- a 7-day pass for costs[1],
- a 30-day pass for costs[2].
A pass bought on day d covers that many consecutive days starting at d (a 7-day pass bought on day 2 covers days 2 to 8). Return the minimum total cost to travel on every listed day.
Examples
Input: days = [1,3,5,20], costs = [3,10,25] Output: 12
Three 1-day passes for days 1, 3 and 5 cost 9, less than a 7-day pass; day 20 adds 3.
Input: days = [2,3,4,5,6,7,30], costs = [2,7,20] Output: 9
One 7-day pass on day 2 covers days 2 to 8, plus a 1-day pass on day 30.
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] Output: 17
A 30-day pass covers days 1 to 30 for 15, and a 1-day pass covers day 31 for 2.
Constraints
- 1 <= len(days) <= 365
- 1 <= days[i] <= 365
- days is strictly increasing
- len(costs) == 3
- 1 <= costs[i] <= 1000
Approaches
- Try every pass at every trip (plain recursion) — time O(3^n) in the worst case, space O(n) for the recursion
Follow-up
What if trips span many years, so the calendar is huge but trips are few? Run the DP over the trips instead of the days: for trip i, three pointers give the first trip not covered by a 1-, 7- or 30-day pass starting at it. The pointers only move forward, so the work is O(n) in the number of trips, independent of the calendar length.
Related problems
Start free on Cariara · Coding problems · System design studio
