Medium

Minimum Cost For Tickets

LAB

Given travel days and pass costs [1-day,7-day,30-day], return the minimum total cost to cover all travel days.

EXAMPLES

Example 1

Input
{
  "days": [
    1,
    4,
    6,
    7,
    8,
    20
  ],
  "costs": [
    2,
    7,
    15
  ]
}

Output
11

FUNCTION SHAPE

days: intArraycosts: intArray→int

SOLUTION NOTE

For each travel day, try all three ticket types. Skip non-travel days. Take minimum cost option.

Reveal reference solution +

pythonREFERENCE

def mincostTickets(self, days: List[int], costs: List[int]) -> int:
    day_set = set(days)

    @cache
    def dp(day):
        if day > days[-1]: return 0
        if day not in day_set: return dp(day + 1)
        return min(
            costs[0] + dp(day + 1),   # 1-day pass
            costs[1] + dp(day + 7),   # 7-day pass
            costs[2] + dp(day + 30)   # 30-day pass
        )

    return dp(days[0])

TimeO(max(days))

SpaceO(max(days))

Open on LeetCode ↗