FunctionRacerProblemsRace

Cheapest Pool Passes

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems