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. - 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 for 7 days: day 2, 3, 4, 5, 6, 7, and 8.
Return the minimum number of dollars you need to travel every day in the given list of days.
Examples
Input: [[1,4,6,7,8,20],[2,7,15]]
Output: 11
Input: [[1,2,3,4,5,6,7,8,9,10,30,31],[2,7,15]]
Output: 17
Hints
Start by considering the most cost-effective pass for each travel day. How would you decide between a 1-day, 7-day, or 30-day pass for a single day?
Think about the problem recursively: if you know the minimum cost to travel up to day `i-1`, how can you compute the minimum cost to travel up to day `i`?
Consider using dynamic programming to store the minimum cost up to each day. How would you define the state transition to cover all possible pass purchases (1-day, 7-day, or 30-day) for each travel day?
Related Problems
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`.