Show problems as
Classic problem #983MediumArrayDynamic Programming

Minimum Cost For Tickets

Real-world version: Cheapest Ferry Passes
Tracked in this browser only
Read Minimum Cost For Tickets on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

You already know which days of the year you will ride the harbour ferry. trips lists those day numbers in strictly increasing order, counting day 1 as the first day of the year.

The ferry sells three kinds of pass and prices gives their costs in this order:

  • prices[0] buys a pass valid for 1 day.
  • prices[1] buys a pass valid for 7 days in a row.
  • prices[2] buys a pass valid for 30 days in a row.

A pass starts on any day you name and stays valid for its whole span of consecutive days, whether or not you ride on each of them. You may buy as many passes as you like, and every day listed in trips has to fall inside the span of at least one pass.

Return the smallest total you can spend.

Examples

Example 1

Input
trips = [3], prices = [5,20,60]
Output
5

A 1-day pass on day 3 covers the only ride and costs 5.

Example 2

Input
trips = [5,6,7,8,9,10,11], prices = [4,10,50]
Output
10

One 7-day pass starting on day 5 stays valid through day 11, so it covers all seven rides, for 10.

Example 3

Input
trips = [12,13,16,21,24,31,37], prices = [50,10,27]
Output
27

One 30-day pass starting on day 12 stays valid through day 41, which covers every ride, for 27.

Example 4

Input
trips = [15,29,44,52,54,55], prices = [11,6,22]
Output
24

Four 7-day passes starting on days 15, 29, 44 and 52 cover the rides, and the last of them covers days 52, 54 and 55 together. Four passes at 6 each is 24.

Example 5

Input
trips = [1,10,25,40], prices = [3,10,30]
Output
12

Four 1-day passes, one on each riding day, cost 12 in total.

Constraints

  • 1 <= trips.length <= 365
  • 1 <= trips[i] <= 365
  • trips is in strictly increasing order.
  • prices.length == 3
  • 1 <= prices[i] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def mincost_tickets(trips: list[int], prices: list[int]) -> int:
Java
public int mincostTickets(int[] trips, int[] prices)

More on the same topics