# Minimum Cost For Tickets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-for-tickets)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-for-tickets
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Grab](https://scaleengineer.com/companies/grab), [Intuit](https://scaleengineer.com/companies/intuit), [Turing](https://scaleengineer.com/companies/turing), [Snap](https://scaleengineer.com/companies/snap), [Zepto](https://scaleengineer.com/companies/zepto)
---
## 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`. 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`

# Approaches
## Brute Force Recursion
This approach directly translates the problem's decision-making process into a recursive function. For each travel day, we explore the three choices of buying a 1-day, 7-day, or 30-day pass. We then recursively calculate the cost for the remaining travel days for each choice and select the one that results in the minimum total cost. This method is intuitive but computationally expensive.
**Time:** O(3^N), where N is the number of travel days. At each travel day, the function can branch into three recursive calls, leading to an exponential growth in the number of operations. · **Space:** O(N), where N is the number of travel days. This space is used by the recursion stack.
**Pros:** Simple to conceptualize and implement directly from the problem statement.
**Cons:** Extremely inefficient due to a massive number of redundant calculations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for most inputs.
### Explanation
We define a helper function, say `solve(index)`, which computes the minimum cost to cover travel days from `days[index]` onwards. The core of this function is to handle the decision at `days[index]`. 

*   **Base Case:** If `index` is greater than or equal to `days.length`, it means we have successfully covered all travel days, and no more cost is needed. We return 0.
*   **Recursive Step:** For the current travel day `days[index]`, we calculate the cost for each of the three ticket options:
    1.  **Buy a 1-day pass:** This covers `days[index]`. The cost is `costs[0]` plus the cost for the rest of the travel plan, which is found by the recursive call `solve(index + 1)`.
    2.  **Buy a 7-day pass:** This pass, bought on `days[index]`, covers all travel for 7 consecutive days (i.e., up to `days[index] + 6`). We need to find the first travel day that falls after this period. We iterate from `index` to find the smallest `j` such that `days[j] >= days[index] + 7`. The cost is `costs[1]` plus `solve(j)`.
    3.  **Buy a 30-day pass:** Similarly, this covers travel up to `days[index] + 29`. We find the smallest `k` such that `days[k] >= days[index] + 30`. The cost is `costs[2]` plus `solve(k)`.

The function then returns the minimum of these three calculated costs. The main function initiates this process by calling `solve(0)`. Because this method re-computes solutions for the same subproblems multiple times, its time complexity is exponential.

```java
class Solution {
    private int[] days;
    private int[] costs;

    public int mincostTickets(int[] days, int[] costs) {
        this.days = days;
        this.costs = costs;
        return solve(0);
    }

    private int solve(int index) {
        if (index >= days.length) {
            return 0;
        }

        // Option 1: 1-day pass
        int cost1 = costs[0] + solve(index + 1);

        // Option 2: 7-day pass
        int nextIndex7 = index;
        while (nextIndex7 < days.length && days[nextIndex7] < days[index] + 7) {
            nextIndex7++;
        }
        int cost7 = costs[1] + solve(nextIndex7);

        // Option 3: 30-day pass
        int nextIndex30 = index;
        while (nextIndex30 < days.length && days[nextIndex30] < days[index] + 30) {
            nextIndex30++;
        }
        int cost30 = costs[2] + solve(nextIndex30);

        return Math.min(cost1, Math.min(cost7, cost30));
    }
}
```
### Algorithm
*   Define a recursive function `solve(index)` that calculates the minimum cost for travel days starting from `days[index]`.
*   The base case: if `index` is out of bounds (i.e., `index >= days.length`), it means all travel is covered, so return 0.
*   For the current travel day `days[index]`, recursively explore three choices:
    1.  **1-day pass:** The cost is `costs[0]` plus the result of `solve(index + 1)`.
    2.  **7-day pass:** Find the next travel day index `j` that is not covered by a pass bought on `days[index]` (i.e., `days[j] > days[index] + 6`). The cost is `costs[1]` plus `solve(j)`.
    3.  **30-day pass:** Find the next travel day index `k` such that `days[k] > days[index] + 29`. The cost is `costs[2]` plus `solve(k)`.
*   Return the minimum cost among the three options.
*   The final answer is the result of the initial call `solve(0)`.

## Top-Down Dynamic Programming (Memoization)
This approach optimizes the brute-force recursion by using memoization, a key technique in dynamic programming. We store the results of subproblems in a cache (e.g., an array or hash map) so that we don't have to re-compute them. The state for our DP is the index of the current travel day we need to cover, `solve(index)`. This avoids the exponential complexity of the naive recursive solution.
**Time:** O(N), where N is the number of travel days. Each state `solve(index)` from 0 to N-1 is computed exactly once. The work inside each state is amortized to O(1) because the pointers used to find the next travel day only advance forward. · **Space:** O(N), where N is the number of travel days. This is for the memoization array and the recursion stack depth.
**Pros:** Highly efficient, as it avoids re-computation of subproblems.; Guaranteed to be fast enough for the given constraints.; Maintains the logical structure of the recursive solution, making it relatively easy to understand.
**Cons:** Has a slight overhead due to recursion function calls compared to an iterative bottom-up approach.; The space complexity is O(N), which might be a concern for problems with very large N, though it's fine for this problem's constraints.
### Explanation
The core idea is to augment the brute-force recursive solution with a memoization table, `memo`, to store the result of `solve(index)` once it's computed. The `memo` array is indexed by the travel day index.

Before computing the result for `solve(index)`, we first check if `memo[index]` already contains a valid result. If it does, we return it immediately, saving computation. If not, we proceed with the calculation as in the brute-force method:

1.  Calculate the cost of buying a 1-day pass.
2.  Calculate the cost of buying a 7-day pass, which involves finding the next travel day not covered by it.
3.  Calculate the cost of buying a 30-day pass similarly.

Once the minimum cost is determined, we store it in `memo[index]` before returning. This ensures that for any given index, the calculation is performed only once. The searches for the next travel day can be done with a simple `while` loop starting from the current index. Over all recursive calls, these searches are efficient, as the pointers only move forward through the `days` array, leading to an overall linear time complexity.

```java
class Solution {
    private int[] days;
    private int[] costs;
    private Integer[] memo;

    public int mincostTickets(int[] days, int[] costs) {
        this.days = days;
        this.costs = costs;
        this.memo = new Integer[days.length];
        return solve(0);
    }

    private int solve(int index) {
        if (index >= days.length) {
            return 0;
        }
        if (memo[index] != null) {
            return memo[index];
        }

        // Option 1: 1-day pass
        int cost1 = costs[0] + solve(index + 1);

        // Option 2: 7-day pass
        int nextIndex7 = index;
        while (nextIndex7 < days.length && days[nextIndex7] < days[index] + 7) {
            nextIndex7++;
        }
        int cost7 = costs[1] + solve(nextIndex7);

        // Option 3: 30-day pass
        int nextIndex30 = index;
        while (nextIndex30 < days.length && days[nextIndex30] < days[index] + 30) {
            nextIndex30++;
        }
        int cost30 = costs[2] + solve(nextIndex30);

        memo[index] = Math.min(cost1, Math.min(cost7, cost30));
        return memo[index];
    }
}
```
### Algorithm
*   Initialize a memoization array `memo` of size `N` (where `N` is `days.length`) with a sentinel value (e.g., `null` or -1) to indicate uncomputed states.
*   Define a recursive function `solve(index)`.
*   Base Case: If `index >= N`, return 0.
*   Memoization Check: If `memo[index]` has been computed, return the stored value.
*   If not computed, calculate the costs for the three pass options as in the brute-force approach:
    1.  `cost1 = costs[0] + solve(index + 1)`
    2.  `cost7 = costs[1] + solve(j)` where `j` is the index of the next travel day after the 7-day pass expires.
    3.  `cost30 = costs[2] + solve(k)` where `k` is the index of the next travel day after the 30-day pass expires.
*   Store the minimum of these three costs in `memo[index]`.
*   Return the value stored in `memo[index]`.

## Bottom-Up Dynamic Programming on Calendar Days
This approach uses bottom-up dynamic programming with a different state definition. Instead of basing our DP state on the index of the `days` array, we use the actual calendar day. We create a DP array, `dp`, where `dp[i]` represents the minimum cost to have covered all travel requirements up to day `i`. This method is iterative and avoids recursion, and the state transitions are very simple.
**Time:** O(W), where W is the value of the last travel day. We iterate once from 1 to W, and each step takes constant time. Building the set takes O(N). Total time is O(N + W). · **Space:** O(W), where W is the value of the last travel day (max 365). This space is for the `dp` array and the `Set` of travel days.
**Pros:** Very clean and simple implementation with a straightforward DP recurrence.; Iterative approach avoids recursion overhead.; Efficient, with time and space complexity bounded by the number of days in a year.
**Cons:** The space complexity depends on the value of the last travel day (`W`), not the number of travel days (`N`). If travel days are sparse (e.g., `days = [1, 365]`), this approach uses more memory than a DP approach based on travel day indices.
### Explanation
We build the solution iteratively from day 1 up to the last travel day. First, we put all travel days into a `Set` for fast lookups. Then, we create a `dp` array, where `dp[i]` will hold the minimum cost for a travel plan covering all necessary travel up to day `i`.

The iteration proceeds as follows:
For each day `i` from 1 to the last travel day:
- If `i` is not a travel day, we don't need to buy any new tickets. The minimum cost is the same as the cost for the previous day, so `dp[i] = dp[i-1]`.
- If `i` is a travel day, we must ensure it's covered. We have three options for the ticket that covers day `i`:
    1.  A 1-day pass bought today: The cost is the total cost up to yesterday (`dp[i-1]`) plus the cost of a 1-day pass (`costs[0]`).
    2.  A 7-day pass ending today (or later): This pass would cover days `i-6` through `i`. The cost would be the total cost up to day `i-7` (`dp[i-7]`) plus the cost of a 7-day pass (`costs[1]`).
    3.  A 30-day pass ending today (or later): Similarly, the cost is the total cost up to day `i-30` (`dp[i-30]`) plus the cost of a 30-day pass (`costs[2]`).
We set `dp[i]` to the minimum of these three possibilities. We use `max(0, ...)` to handle boundary conditions for days near the beginning of the year. The final answer is the value in `dp` at the index of the last travel day.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1];
        int[] dp = new int[lastDay + 1];
        Set<Integer> travelDays = new HashSet<>();
        for (int day : days) {
            travelDays.add(day);
        }

        for (int i = 1; i <= lastDay; i++) {
            if (!travelDays.contains(i)) {
                dp[i] = dp[i - 1];
            } else {
                int cost1 = dp[i - 1] + costs[0];
                int cost7 = dp[Math.max(0, i - 7)] + costs[1];
                int cost30 = dp[Math.max(0, i - 30)] + costs[2];
                dp[i] = Math.min(cost1, Math.min(cost7, cost30));
            }
        }
        return dp[lastDay];
    }
}
```
### Algorithm
*   Let `W` be the last day in the `days` array.
*   Create a `Set` of travel days for efficient O(1) lookups.
*   Create a DP array, `dp`, of size `W + 1`, where `dp[i]` will store the minimum cost to cover travel up to day `i`.
*   Initialize `dp[0] = 0`.
*   Iterate with `i` from 1 to `W`:
    *   If day `i` is not a travel day, no new ticket is needed, so `dp[i] = dp[i-1]`.
    *   If day `i` is a travel day, we must cover it. Calculate the cost by considering three ways to cover day `i`:
        1.  With a 1-day pass: `dp[i-1] + costs[0]`.
        2.  With a 7-day pass: `dp[max(0, i-7)] + costs[1]`.
        3.  With a 30-day pass: `dp[max(0, i-30)] + costs[2]`.
    *   Set `dp[i]` to the minimum of these three costs.
*   The final answer is `dp[W]`.

# Solutions
### Java

```java
class Solution {
private
  static final int[] T = new int[]{1, 7, 30};
private
  int[] costs;
private
  int[] days;
private
  int[] f;
private
  int n;
public
  int mincostTickets(int[] days, int[] costs) {
    n = days.length;
    f = new int[n];
    this.costs = costs;
    this.days = days;
    Arrays.fill(f, -1);
    return dfs(0);
  }
private
  int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != -1) {
      return f[i];
    }
    int res = Integer.MAX_VALUE;
    for (int k = 0; k < 3; ++k) {
      int j = lowerBound(days, days[i] + T[k]);
      res = Math.min(res, costs[k] + dfs(j));
    }
    f[i] = res;
    return res;
  }
private
  int lowerBound(int[] days, int x) {
    int left = 0, right = days.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (days[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution { public: vector < int > t = { 1 , 7 , 30 }; vector < int > days ; vector < int > costs ; vector < int > f ; int n ; int mincostTickets ( vector < int >& days , vector < int >& costs ) { n = days . size (); this -> days = days ; this -> costs = costs ; f . assign ( n , - 1 ); return dfs ( 0 ); } int dfs ( int i ) { if ( i >= n ) return 0 ; if ( f [ i ] != - 1 ) return f [ i ]; int res = INT_MAX ; for ( int k = 0 ; k < 3 ; ++ k ) { int j = lower_bound ( days . begin (), days . end (), days [ i ] + t [ k ]) - days . begin (); res = min ( res , costs [ k ] + dfs ( j )); } f [ i ] = res ; return res ; } };
```

### Python

```python
class Solution : def mincostTickets ( self , days : List [ int ], costs : List [ int ]) -> int : @ cache def dfs ( i ): if i >= len ( days ): return 0 res = inf for c , d in zip ( costs , [ 1 , 7 , 30 ]): j = bisect_left ( days , days [ i ] + d ) res = min ( res , c + dfs ( j )) return res return dfs ( 0 )
```