983. 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

Approach 01:

class Solution {
public:
    vector<int> memo;

    // Recursive helper function
    int solve(int index, const vector<int>& days, const vector<int>& costs) {
        // Base case: if all days are processed, return 0
        if (index >= days.size()) {
            return 0;
        }

        // If the result for this index is already computed, return it
        if (memo[index] != -1) {
            return memo[index];
        }

        // Option 1: Buy a 1-day pass
        int oneDayPass = costs[0] + solve(index + 1, days, costs);

        // Find the next index for 7-day pass
        int nextIndexForSevenDay = index;
        while (nextIndexForSevenDay < days.size() && days[nextIndexForSevenDay] < days[index] + 7) {
            ++nextIndexForSevenDay;
        }
        int sevenDayPass = costs[1] + solve(nextIndexForSevenDay, days, costs);

        // Find the next index for 30-day pass
        int nextIndexForThirtyDay = index;
        while (nextIndexForThirtyDay < days.size() && days[nextIndexForThirtyDay] < days[index] + 30) {
            ++nextIndexForThirtyDay;
        }
        int thirtyDayPass = costs[2] + solve(nextIndexForThirtyDay, days, costs);

        // Return and memoize the minimum cost
        memo[index] = min({oneDayPass, sevenDayPass, thirtyDayPass});
        return memo[index];
    }

    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // Initialize memoization array with -1
        memo.assign(days.size(), -1);
        return solve(0, days, costs);
    }
};

class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        # Memoization array
        memo = [-1] * len(days)

        # Recursive helper function
        def solve(index: int) -> int:
            # Base case: if all days are processed, return 0
            if index >= len(days):
                return 0

            # If the result for this index is already computed, return it
            if memo[index] != -1:
                return memo[index]

            # Option 1: Buy a 1-day pass
            oneDayPass = costs[0] + solve(index + 1)

            # Find the next index for 7-day pass
            nextIndexForSevenDay = index
            while nextIndexForSevenDay < len(days) and days[nextIndexForSevenDay] < days[index] + 7:
                nextIndexForSevenDay += 1
            sevenDayPass = costs[1] + solve(nextIndexForSevenDay)

            # Find the next index for 30-day pass
            nextIndexForThirtyDay = index
            while nextIndexForThirtyDay < len(days) and days[nextIndexForThirtyDay] < days[index] + 30:
                nextIndexForThirtyDay += 1
            thirtyDayPass = costs[2] + solve(nextIndexForThirtyDay)

            # Return and memoize the minimum cost
            memo[index] = min(oneDayPass, sevenDayPass, thirtyDayPass)
            return memo[index]

        # Start the recursive process from the first index
        return solve(0)

Time Complexity

• Recursive Function with Memoization:
  • The function solve is called once for each day in the days array, resulting in \( O(n) \) unique states, where \( n \) is the number of days.
  • Each state computation involves a constant number of operations (three while loops and comparisons) independent of the number of days.
• Overall Time Complexity:

  The total time complexity is \( O(n) \), where \( n \) is the size of the days array.

Space Complexity

• Memoization Table:
  • The memoization table stores results for \( O(n) \) states, requiring \( O(n) \) space, where \( n \) is the size of the days array.
• Auxiliary Space:
  • The recursive stack depth is \( O(n) \), corresponding to the size of the days array.
• Overall Space Complexity:

  The total space complexity is \( O(n) \), where \( n \) is the size of the days array.