# Leetcode 983. Minimum Cost For Tickets

[link](https://leetcode.com/problems/minimum-cost-for-tickets)

---

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. Each day is an integer from 1 to 365.

Train tickets are sold in three different ways:

- a 1-day pass is sold for costs[0] dollars,
- a 7-day pass is sold for costs[1] dollars, and
- a 30-day pass is sold for costs[2] dollars.
The passes allow that many days of consecutive travel.

- For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

#### Example 1:

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:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

#### Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.

#### Constraints:

- 1 <= days.length <= 365
- 1 <= days[i] <= 365
- days is in strictly increasing order.
- costs.length == 3
- 1 <= costs[i] <= 1000

---

The base case of the recursion checks if i has reached the end of the list of travel days. If so, it returns a cost of 0 because no more days need to be covered.

It checks if the result for the current position i has already been calculated and stored in the dp dictionary. If it has, it retrieves and returns the stored result to avoid redundant calculations.

It initializes dp[i] with a value of positive infinity, which serves as a placeholder for storing the minimum cost for the current position.

It iterates through three durations (1-day, 7-day, and 30-day passes) and their corresponding costs, using a loop. For each duration d, it calculates the cost of buying a pass and looks for the next available travel day within the duration.

It updates dp[i] with the minimum cost among all possible durations, considering the cost of the pass plus the cost of traveling for the remaining days starting from the next available day.

After considering all possible durations and updating dp[i] with the minimum cost, the function returns the minimum cost for the current position i.

Finally, the mincostTickets method is called with an initial position of 0 (i.e., starting from the first travel day), and it returns the minimum cost for traveling on the given days using the provided ticket costs.

#### Solution 1

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = {}
        
        def dfs(i):
            if i == len(days):
                return 0
            if i in dp:
                return dp[i]

            dp[i] = float("inf")
            
            for d, c in zip([1, 7, 30], costs):
                j = i
                while j < len(days) and days[j] < days[i] + d:
                    j += 1

                dp[i] = min(dp[i], c + dfs(j))

            return dp[i]

        return dfs(0)  

O(T): O(38 * n)
O(S): O(n)