Minimum Cost For Tickets
You have planned some train travel a year in advance. The days of the year on which you will travel are given as an integer array days, sorted in ascending order, where each day is a number between 1 and 365.
Train tickets are sold three ways: a 1-day pass costs costs[0] dollars, a 7-day pass costs costs[1] dollars, and a 30-day pass costs costs[2] dollars. A pass bought on a given day covers that many consecutive calendar days starting from it, whether or not you travel on all of them.
Return the minimum number of dollars needed to cover every day in days.
days = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15]
11
Buy a 1-day pass on day 1 for 2, a 7-day pass on day 4 covering days 4 through 10 for 7, and a 1-day pass on day 20 for 2. The total is 11.
days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], costs = [2, 7, 15]
17
Buy a 30-day pass on day 1 for 15, covering days 1 through 30, then a 1-day pass on day 31 for 2. Buying 1-day passes for all twelve days would cost 24, and the ten early days alone would cost 20.
1 <= days.length <= 3651 <= days[i] <= 365, strictly increasingcosts.length == 3and1 <= costs[i] <= 1000