Minimum Cost for Tickets
Medium · dynamic programming
You will ride the tram on certain days of the year, numbered from 1 to 365. The list days holds those days in strictly increasing order.
The tram company sells three kinds of pass:
- a 1-day pass for
costs[0], valid on the day you start it; - a 7-day pass for
costs[1], valid on the day you start it and the next 6 days; - a 30-day pass for
costs[2], valid on the day you start it and the next 29 days.
You can buy as many passes as you like and start each one on any day. Passes may overlap. You must hold a valid pass on every day listed in days. Return the smallest total price you can pay.
Examples
Example 1
Input: days = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15]
Output: 11
Buy a 1-day pass for day 1 (2), a 7-day pass for days 4 to 10 (7) and a 1-day pass for day 20 (2). Total 11.
Example 2
Input: days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], costs = [2, 7, 15]
Output: 17
Three 1-day passes cover days 1 to 3 (6), a 7-day pass covers days 4 to 10 (7), and two 1-day passes cover days 30 and 31 (4). Total 17.
Example 3
Input: days = [5], costs = [9, 4, 6]
Output: 4
Here the 7-day pass is cheaper than the 1-day pass, so buy it for the single trip.
Constraints
- 1 <= len(days) <= 365
- 1 <= days[i] <= 365, and days is strictly increasing
- len(costs) == 3
- 1 <= costs[i] <= 1000