# LeetCode 983: Minimum Cost For Tickets

## Problem Restatement

We are given two arrays:

```python
days
costs
```

`days` contains the days of the year when we need to travel.

`costs` contains the prices of three ticket types:

| Ticket | Cost |
|---|---:|
| 1-day pass | `costs[0]` |
| 7-day pass | `costs[1]` |
| 30-day pass | `costs[2]` |

A pass covers consecutive calendar days.

For example, if we buy a 7-day pass on day `3`, it covers:

```python
3, 4, 5, 6, 7, 8, 9
```

We need to return the minimum total cost needed to cover every travel day.

The official constraints are `1 <= days.length <= 365`, `1 <= days[i] <= 365`, `days` is strictly increasing, `costs.length == 3`, and `1 <= costs[i] <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Travel days `days` and ticket prices `costs` |
| Output | Minimum total cost |
| Pass durations | `1`, `7`, and `30` calendar days |
| Important detail | We only need to cover the days listed in `days` |

Function shape:

```python
def mincostTickets(days: list[int], costs: list[int]) -> int:
    ...
```

## Examples

Example 1:

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

One optimal plan is:

| Purchase | Covers | Cost |
|---|---|---:|
| 1-day pass on day `1` | day `1` | `2` |
| 7-day pass on day `3` | days `3` through `9` | `7` |
| 1-day pass on day `20` | day `20` | `2` |

Total:

```python
2 + 7 + 2 = 11
```

Answer:

```python
11
```

Example 2:

```python
days = [1,2,3,4,5,6,7,8,9,10,30,31]
costs = [2,7,15]
```

One optimal plan is:

| Purchase | Covers | Cost |
|---|---|---:|
| 30-day pass on day `1` | days `1` through `30` | `15` |
| 1-day pass on day `31` | day `31` | `2` |

Total:

```python
15 + 2 = 17
```

Answer:

```python
17
```

These match the official examples.

## First Thought: Try Every Ticket Choice

At each uncovered travel day, we can buy one of three passes:

```python
1-day pass
7-day pass
30-day pass
```

Then we skip all travel days covered by that pass and solve the remaining problem.

This gives a natural recursive solution.

For example, if the current travel day is `days[i]`, and we buy a 7-day pass, it covers all travel days less than:

```python
days[i] + 7
```

Then we continue from the first travel day not covered by that pass.

Without memoization, this repeats the same subproblems many times.

## Key Insight

Define:

```python
dp(i) = minimum cost to cover travel days from index i to the end
```

At index `i`, we try each ticket type.

If the pass duration is `duration`, then buying that pass costs:

```python
cost + dp(next_index)
```

where `next_index` is the first index whose travel day is not covered by the pass.

The answer is:

```python
dp(0)
```

Because `days` is strictly increasing, we can find `next_index` by moving forward or by binary search.

## Algorithm

Use recursion with memoization.

For `dfs(i)`:

1. If `i == len(days)`, all travel days are covered, so return `0`.
2. Try a 1-day pass.
3. Try a 7-day pass.
4. Try a 30-day pass.
5. For each pass, find the first travel day not covered.
6. Return the minimum cost among the three choices.

For a pass bought on `days[i]` with duration `d`, it covers days:

```python
days[i], days[i] + 1, ..., days[i] + d - 1
```

So the first uncovered day must satisfy:

```python
days[j] >= days[i] + d
```

## Correctness

Let `dfs(i)` be the minimum cost to cover all travel days from index `i` onward.

If `i == len(days)`, there are no remaining travel days, so the minimum cost is `0`.

For any `i < len(days)`, the travel day `days[i]` must be covered by some pass. In an optimal solution, consider the first pass that covers `days[i]`. That pass has duration either `1`, `7`, or `30`.

If we choose a pass with duration `d`, it covers every travel day less than `days[i] + d`. The next remaining travel day is therefore the first index `j` such that:

```python
days[j] >= days[i] + d
```

After buying that pass, the remaining optimal cost is exactly `dfs(j)`.

The algorithm tries all three possible pass durations and takes the minimum. Therefore, it considers the first decision of every possible optimal plan.

By memoizing `dfs(i)`, each subproblem is solved once. Since `dfs(0)` represents covering all travel days, the returned value is the minimum total cost.

## Complexity

Let `n = len(days)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | There are `n` states, and each state does up to three binary searches |
| Space | `O(n)` | Memoization and recursion stack |

Because `n <= 365`, this is easily fast enough.

## Implementation

```python
from functools import cache
from bisect import bisect_left

class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        durations = [1, 7, 30]
        n = len(days)

        @cache
        def dfs(i: int) -> int:
            if i == n:
                return 0

            best = float("inf")

            for duration, cost in zip(durations, costs):
                next_day = days[i] + duration
                j = bisect_left(days, next_day)
                best = min(best, cost + dfs(j))

            return best

        return dfs(0)
```

## Code Explanation

We define the ticket durations:

```python
durations = [1, 7, 30]
```

The recursive function means:

```python
dfs(i)
```

minimum cost to cover travel days from `days[i]` onward.

If all travel days are already covered:

```python
if i == n:
    return 0
```

For each ticket type:

```python
for duration, cost in zip(durations, costs):
```

we compute the first calendar day not covered by the pass:

```python
next_day = days[i] + duration
```

Then we find the first index with a travel day at least `next_day`:

```python
j = bisect_left(days, next_day)
```

The total cost for this choice is:

```python
cost + dfs(j)
```

We keep the cheapest choice:

```python
best = min(best, cost + dfs(j))
```

Finally:

```python
return dfs(0)
```

returns the minimum cost to cover all travel days.

## Alternative Bottom-Up Implementation

Since the calendar has only `365` days, we can also use daily DP.

Let:

```python
dp[day] = minimum cost to cover all travel days up to this calendar day
```

If `day` is not a travel day, the cost stays the same as yesterday.

If `day` is a travel day, choose the cheapest pass ending at this day.

```python
class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        travel_days = set(days)
        last_day = days[-1]
        dp = [0] * (last_day + 1)

        for day in range(1, last_day + 1):
            if day not in travel_days:
                dp[day] = dp[day - 1]
            else:
                one_day = dp[max(0, day - 1)] + costs[0]
                seven_day = dp[max(0, day - 7)] + costs[1]
                thirty_day = dp[max(0, day - 30)] + costs[2]

                dp[day] = min(one_day, seven_day, thirty_day)

        return dp[last_day]
```

This version runs in `O(365)` time, which is constant under the given constraints.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.mincostTickets([1, 4, 6, 7, 8, 20], [2, 7, 15]) == 11
    assert s.mincostTickets([1,2,3,4,5,6,7,8,9,10,30,31], [2, 7, 15]) == 17
    assert s.mincostTickets([1], [2, 7, 15]) == 2
    assert s.mincostTickets([1, 7, 30, 365], [3, 8, 20]) == 12
    assert s.mincostTickets([1, 2, 3, 4, 5, 6, 7], [3, 8, 20]) == 8

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[1,4,6,7,8,20]`, `[2,7,15]` | `11` | Standard sample |
| `[1,2,3,4,5,6,7,8,9,10,30,31]`, `[2,7,15]` | `17` | 30-day pass is useful |
| `[1]`, `[2,7,15]` | `2` | One travel day |
| `[1,7,30,365]`, `[3,8,20]` | `12` | Sparse travel days |
| `[1,2,3,4,5,6,7]`, `[3,8,20]` | `8` | One 7-day pass is best |