578. Minimum Cost For Tickets
You have mapped out a year of train trips. days is a strictly increasing list of the calendar days (each between 1 and 365) on which you will travel. The railway sells three kinds of passes, priced by costs: costs[0] buys a pass valid for 1 consecutive day, costs[1] for 7 consecutive days, and costs[2] for 30 consecutive days. A pass bought on day d covers days d, d+1, …, up to the end of its window.
Your function receives the integer array days and the 3-element integer array costs, and must return the smallest total amount of money that keeps you covered on every travel day. It is fine (and sometimes optimal) for a pass to also cover days you don't travel.
Example 1:
Input: days = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15]
Output: 11
Explanation: Buy a 1-day pass for day 1 (cost 2), a 7-day pass on day 4 covering days 4–10 (cost 7), and a 1-day pass for day 20 (cost 2). Total 2 + 7 + 2 = 11.
Example 2:
Input: days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], costs = [2, 7, 15]
Output: 17
Explanation: A 30-day pass bought on day 1 covers days 1–30 (cost 15), then a 1-day pass handles day 31 (cost 2). Total 17.
Constraints:
- 1 ≤ days.length ≤ 365
- 1 ≤ days[i] ≤ 365
- days is strictly increasing
- costs.length == 3
- 1 ≤ costs[i] ≤ 1000
Hints:
Greedy fails: whether a 7-day pass is worth it on day 4 depends on how many travel days fall in the next week — you need to compare futures, which is what dynamic programming does.
Define dp[d] = cheapest way to cover all travel days up to calendar day d. If d is not a travel day, dp[d] = dp[d-1]. What are the three choices when d IS a travel day?
On a travel day d: the last pass you're holding is either a 1-day (dp[d-1] + costs[0]), a 7-day (dp[d-7] + costs[1]), or a 30-day (dp[d-30] + costs[2]). Clamp negative indices to 0 and take the min.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: days = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15]
Expected output: 11