Planning Rail Passes

Medium

You already know which days of the year you will take the train: the day numbers (1 to 365) are listed in increasing order in trip_days. The ticket office sells three passes: - a 1-day pass for prices[0]; - a 7-day pass for prices[1]; - a 30-day pass for prices[2]. A pass is valid from the day you buy it: a 7-day pass bought on day 10 covers days 10 through 16. Return the smallest amount you need to spend so that every day in trip_days is covered by at least one pass.

Example 1

trip_days=[3, 4, 5, 6, 40], prices=[3, 10, 50] → 13

Days 3 to 6 are four trips in a row: a weekly pass for 10 beats four daily ones (12). Day 40 gets a daily pass for 3. Total 13.

Example 2

trip_days=[1, 10, 20, 29], prices=[4, 9, 12] → 12

All trips fall within the 30 days from day 1 to day 30, so a single monthly pass for 12 is the cheapest option.

Example 3

trip_days=[100], prices=[7, 2, 5] → 2

Constraints

1 ≤ len(trip_days) ≤ 365
1 ≤ trip_days[i] ≤ 365, strictly increasing
len(prices) = 3
1 ≤ prices[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

trip_days=[3, 4, 5, 6, 40], prices=[3, 10, 50]

Expected

Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.