hardDynamic Programming 1DPure DSA~35 min
Cheapest Set of Travel Passes to Cover All Trip Days
You must travel on certain days of the year. Passes come in 1-day, 7-day, and 30-day durations at fixed prices. Choose passes to cover every travel day at minimum total cost.
Problem
Given a sorted array days of the days you will travel (1..365) and an array costs = [c1, c7, c30] for 1-day, 7-day, and 30-day passes, return the minimum cost to cover all travel days. A k-day pass bought on day d covers days d..d+k-1.
Input
A sorted array days and a length-3 array costs.
Output
An integer: the minimum total pass cost.
Constraints
- 1 <= days.length <= 365
- 1 <= days[i] <= 365 and strictly increasing
- 1 <= costs[i] <= 1000
Examples
Example 1
Input
days = [1,4,6,7,8,20], costs = [2,7,15]
Output
11
A 7-day pass covers days 1-7 (cost 7), plus single passes for 8 and 20 (2 + 2).
Example 2
Input
days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output
17
A 30-day pass on day 1 (15) covers all but nothing extra; plus a 1-day for day 31 (2).