Minimum Cost For Tickets — LeetCode 983 Python Solution

The problem

You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days.

Example

Input

days = [1,4,6,7,8,20], costs = [2,7,15]

Output

11

Explanation

For example, here is one way to buy passes that lets you travel your travel plan:

Python solution

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            ans = inf
            for c, v in zip(costs, valid):
                j = bisect_left(days, days[i] + v)
                ans = min(ans, c + dfs(j))
            return ans

        n = len(days)
        valid = [1, 7, 30]
        return dfs(0)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 983. Minimum Cost For Tickets is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems