Minimum Cost For Tickets
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.
Train tickets are sold in three different ways:
- a 1-day pass is sold for
costs[0]dollars, - a 7-day pass is sold for
costs[1]dollars, and - a 30-day pass is sold for
costs[2]dollars.
The passes allow that many days of consecutive travel.
- For example, if we get a 7-day pass on day
2, then we can travel for7days:2,3,4,5,6,7, and8.
Return the minimum number of dollars you need to travel every day in the given list of days.
Example 1
Input
days = [1,4,6,7,8,20], costs = [2,7,15]Output
11Buying a 1-day pass for day 1, a 7-day pass covering days 3 through 9, and a 1-day pass for day 20 costs 11 dollars and covers all travel days.
Example 2
Input
days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]Output
17Buying a 30-day pass covering days 1 through 30 and a 1-day pass for day 31 costs 17 dollars and covers all travel days.
Constraints
- 1 <= days.length <= 365
- 1 <= days[i] <= 365
- days is in strictly increasing order.
- costs.length == 3
- 1 <= costs[i] <= 1000