Cheapest Pool Passes
You will swim on the days listed in days, in increasing order. The pool sells several kinds of pass: a pass of kind k costs costs[k] and lets you in on lengths[k] consecutive days, starting on whatever day you choose. You may buy any number of passes of each kind.
Return the least total cost of passes that cover every swim day. With no swim days, return 0.
Example 1
days [2,3,5,9,10,11,30]
costs [3,8]
lengths [1,5]
returns 19
A 5-day pass from day 2 covers days 2, 3 and 5, another from day 9 covers 9, 10 and 11, and a 1-day pass covers day 30: 8 + 8 + 3 = 19.
Example 2
days [1,2,3,4,5,6,7]
costs [4,15]
lengths [2,7]
returns 15
One 7-day pass for 15 is cheaper than the four 2-day passes (16) needed to cover seven days.
Constraints
0 <= len(days) <= 1001 <= days[i] <= 365, strictly increasing1 <= len(costs) <= 4,len(lengths) == len(costs)1 <= lengths[k] <= 601 <= costs[k] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Coins From Either EndMedium
- Count DerangementsMedium
- Count the Free PlotsMedium
- Dice Sum WaysMedium
- Fairest Stone SplitMedium
- Fewest Perfect SquaresMedium
- Gems That ClashMedium
- Hands That Hit the TargetMedium