983. Minimum Cost For Tickets

Problem Description

In this train traveling problem, you are given an integer array days, which represents each day in the year you will travel by train. The days are within the range from 1 to 365. The goal is to find the minimum cost needed to purchase train tickets to cover all those traveling days within a year.

There are three types of train passes you can buy:

A 1-day pass for costs[0] dollars.
A 7-day pass for costs[1] dollars.
A 30-day pass for costs[2] dollars.

A pass allows you to travel for that number of consecutive days. For instance, if you buy a 7-day pass on day 2, you can travel from day 2 to day 8 inclusively.

You need to determine the minimum total cost to buy passes such that you can travel on all the days listed in the array days.

Intuition

To tackle this problem, we need to consider that buying a longer-term pass (7-day or 30-day) might be cheaper in the long run even if we don't use all of its valid days. Our solution must weigh the costs and benefits of each type of pass for each travel day.

We can think about the problem in terms of decision-making on each traveling day: should we buy a 1-day, 7-day, or 30-day pass? After buying a pass, we'd like to know "when do we have to make the next decision?” This leads to a recursive solution where we try all possible pass purchases and choose the one with the lowest overall cost.

For each day in days we are traveling, we have three choices: buy a 1-day pass, buy a 7-day pass, or buy a 30-day pass. After we buy a pass, we will skip to the next day that is outside the range of the pass. For example, if we're considering buying a 7-day pass on day i, the next decision would be made for the first day after those 7 days.

The mincostTickets function uses dynamic programming to avoid recalculating the minimum cost for days that have already been processed. A dfs function is used to find the minimum cost recursively, starting from the first day in days. The @cache decorator is used to memoize results, which saves the results of subproblems and dramatically reduces the time complexity.*

An array could also be used to cache results, but using the @cache decorator is cleaner and avoids the need to explicitly manage the caching logic.

Using binary search (bisect_left from the bisect module), we determine the day to continue the search from after buying a particular pass. The bisect_left function finds the position to insert an element to keep the list sorted and is used here to find the first travel day that is not covered by the current pass being considered.

The recursion's base case is when i goes beyond the last travel day, returning a cost of 0 because no further tickets need to be purchased.

We iterate through all types of passes, calculate the total cost if we bought a particular type of pass, and then take the minimum of those costs. The result from the dfs function called with 0, the first day, gives us the minimum cost required for all the travel days.

*As of the knowledge cutoff date in September 2021, the @cache decorator is available in Python 3.9 and later as part of the functools module.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution takes a dynamic programming approach using recursion with memoization to keep track of the subproblems that have already been solved. Here's a breakdown of the implementation:

Recursion: The core algorithm is a recursive function dfs(i), which computes the minimum cost starting from the i-th travel day in the days array. If i is equal to or greater than the length of days, it means all travel days have been covered, and the function returns 0.
Memoization: The use of the @cache decorator from the functools module automatically stores the results of the recursive calls. This way, when the function is called again with the same i, it returns the stored result instead of recomputing it. This memoization significantly speeds up the execution by eliminating duplicate calculations.
Binary Search: The bisect_left function from the bisect module efficiently finds the smallest index j at which the day days[i] + d could be inserted to maintain the sorted order. Here, d represents the duration of the pass (1, 7, or 30 days), and finding j allows us to determine the first day that is not covered by the pass. This helps us move to the next subproblem without iterating over each day.
Minimum Cost Calculation: The recursive function tries to simulate buying each type of pass (1-day, 7-day, or 30-day), and for each case, it adds the cost of the pass c to the result of the recursive call for the next uncovered day dfs(j). Then, it stores the minimum of these calculated costs in the variable res.

The dynamics of the function are as follows:

We iterate over each type of pass using a loop for c, d in zip(costs, [1, 7, 30]):.
We find the next index j to call our function recursively via j = bisect_left(days, days[i] + d).
We calculate the cost of buying the current pass and add it to the cost of all future decisions: res = min(res, c + dfs(j)).
After trying all pass options for day i, res will contain the minimum cost to cover day i and all subsequent days.

After the setup of the recursive function and decorators, the solution is initiated by calling return dfs(0). The result is the minimum total cost to purchase train tickets for all the traveling days.

This algorithm efficiently decides the best pass to buy for each travel day, considering all the possible options and their costs, to come up with the minimum total cost for all travel days.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume the days array in which we will travel is given by [1, 4, 6, 7, 8, 20], and the costs of train passes are available as [2, 7, 15] for 1-day, 7-day, and 30-day passes, respectively.

We start by calling the dfs function with i = 0, which corresponds to the first traveling day, day 1.

Day 1 Decision:
- Buy a 1-day pass for costs[0] or $2. Our next decision will be on day 4 (next travel day after day 1).
- Buy a 7-day pass for costs[1] or $7. The next decision day will be day 20 (as days 4, 6, 7, and 8 all fall within the 7-day period starting day 1).
- Buy a 30-day pass for costs[2] or $15. Since the 30-day pass covers the entire days array in this example, this would mean no more decisions are necessary.
Subsequent Decisions:
- If we bought a 1-day pass for the first day, on day 4, we face similar options (buy a 1-day, 7-day, or 30-day pass), and the same applies for days 6, 7, 8, and 20. Each option's cost is calculated and added to the initial $2.
- If we chose a 7-day pass, we next buy a pass on day 20. Here, since it’s the last day, we'd only consider a 1-day pass, which adds $2 to the initial $7.
Memoization:
- During the process, all calculated costs are stored, and if a day is reached that has been previously calculated, we simply use the stored value.
Recursive Calls and Minimum Cost Calculation:
- The dfs(4) call calculates the minimum cost from day 4 and so on. For example, if dfs(4) returns $9 (cheapest way to cover days 4, 6, 7, 8, 20), the total cost of buying a 1-day pass on day 1 and using the optimal strategy onward is $2 + $9 = $11.
Final Decision:
- After exploring all options, we take the minimum total cost to purchase train tickets for all travel days. In our case, it's min($2 + dfs(4), $7 + dfs(20), $15).

Assuming dfs(4) returns $9 (example value), dfs(20) returns $2, the final costs would be $11, $9, and $15, and the minimum cost is thus $9. So buying a 7-day pass on day 1 and a 1-day pass on day 20 would be the optimal solution here.

Solution Implementation

1from bisect import bisect_left
2from functools import lru_cache
3
4class Solution:
5    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
6        # Using lru_cache from functools to memoize results of recursive calls
7        # This will store results of the subproblems so they do not need to be recomputed
8        @lru_cache(maxsize=None)
9        def min_cost_from_day(index):
10            # Base case: when all days have been covered
11            if index >= len(days):
12                return 0
13          
14            # Initialize result as infinity to ensure any minimum will be taken
15            result = float('inf')
16          
17            # Iterate over each type of ticket to cover future travel
18            for ticket_cost, validity_duration in zip(costs, [1, 7, 30]):
19                # Find the next day index when the current ticket will be expired
20                next_index = bisect_left(days, days[index] + validity_duration)
21                # Calculate the cost if we select current ticket and call recursively for the remaining days
22                total_cost = ticket_cost + min_cost_from_day(next_index)
23                # Update the minimum result
24                result = min(result, total_cost)
25          
26            # Return the minimum cost found
27            return result
28
29        # Start from the first day we have in the list
30        return min_cost_from_day(0)
31

1public class Solution {
2
3    // Define constants for pass durations
4    private static final int[] PASS_DURATIONS = new int[]{1, 7, 30};
5
6    // Variables to store costs, days, and memoized values
7    private int[] passCosts;
8    private int[] travelDays;
9    private int[] memo;
10    private int totalDays;
11
12    // Method to calculate the minimum cost of tickets for given travel days and ticket costs
13    public int mincostTickets(int[] days, int[] costs) {
14        totalDays = days.length;
15        memo = new int[totalDays];
16        this.passCosts = costs;
17        this.travelDays = days;
18
19        // Fill memo array with default values to denote not calculated
20        Arrays.fill(memo, -1);
21
22        // Start DFS from the first day
23        return dfs(0);
24    }
25
26    // Helper method to perform Depth-First Search (DFS) 
27    private int dfs(int currentIndex) {
28        // Base case: if the currentIndex is beyond the last day, no cost is needed
29        if (currentIndex >= totalDays) {
30            return 0;
31        }
32
33        // If the cost has already been computed, return it
34        if (memo[currentIndex] != -1) {
35            return memo[currentIndex];
36        }
37
38        // Initialize result as the maximum value 
39        int result = Integer.MAX_VALUE;
40
41        // Consider all types of passes
42        for (int k = 0; k < 3; ++k) {
43            // Find the index of the next day right after the pass expires
44            int nextIndex = lowerBound(travelDays, travelDays[currentIndex] + PASS_DURATIONS[k]);
45
46            // Calculate the minimum cost using the chosen pass
47            result = Math.min(result, passCosts[k] + dfs(nextIndex));
48        }
49
50        // Save result to memo array
51        memo[currentIndex] = result;
52
53        // Return the final minimized cost
54        return result;
55    }
56
57    // Helper method to find the lower bound index for a given day (binary search)
58    private int lowerBound(int[] days, int targetDay) {
59        int left = 0, right = days.length;
60        while (left < right) {
61            int mid = left + (right - left) / 2;
62          
63            // If mid is less than target, ignore the left half
64            if (days[mid] < targetDay) {
65                left = mid + 1;
66            } else {
67                // If mid is greater or equal to target, ignore the right half
68                right = mid;
69            }
70        }
71        // Return the lower bound index
72        return left;
73    }
74}
75

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5using namespace std;
6
7class Solution {
8public:
9    vector<int> ticketDurations = {1, 7, 30}; // Durations of tickets in days
10    vector<int> travelDays; // Days on which the person is traveling
11    vector<int> ticketCosts; // Costs corresponding to tickets of each duration
12    vector<int> dpCache; // Cache for storing results of subproblems
13    int totalDays; // Total number of travel days
14
15    // Calculates the minimum cost of all tickets needed for traveling on specific days
16    int mincostTickets(vector<int>& days, vector<int>& costs) {
17        totalDays = days.size(); // Set the total number of travel days
18        this->travelDays = days; // Copy travel days to member variable
19        this->ticketCosts = costs; // Copy ticket costs to member variable
20        dpCache.assign(totalDays, -1); // Initialize the cache with -1, indicating uncomputed states
21        return dfs(0); // Start the DFS traversal from day index 0
22    }
23
24    // Depth-First Search function to calculate the minimum cost of tickets starting from day index 'i'
25    int dfs(int i) {
26        if (i >= totalDays) return 0; // If all travel days are covered, no more cost is needed
27        if (dpCache[i] != -1) return dpCache[i]; // If result is already computed, return it
28      
29        int minCost = INT_MAX; // Initialize the minimum cost to max value as we are looking for the minimum
30        for (int k = 0; k < 3; ++k) { // Iterate over the three types of tickets
31            // Find the next travel day index which is outside the current ticket duration
32            int j = lower_bound(travelDays.begin(), travelDays.end(), travelDays[i] + ticketDurations[k]) - travelDays.begin();
33            // Calculate cost and find minimum cost by trying all ticket types
34            minCost = min(minCost, ticketCosts[k] + dfs(j));
35        }
36        dpCache[i] = minCost; // Store the result in the cache before returning
37        return minCost; // Return the minimum cost for tickets starting from day index 'i'
38    }
39};
40

1function mincostTickets(days: number[], costs: number[]): number {
2    const totalDays = days.length; // Number of days you are traveling
3    const lastDay = days[totalDays - 1] + 1; // The last day of travel (plus one for indexing purposes)
4    const [cost1DayPass, cost7DayPass, cost30DayPass] = costs; // Destructure costs array to name the individual pass costs
5    let dp: number[] = new Array(lastDay).fill(0); // Dynamic programming array to store minimum costs up to each day
6
7    // Iterate over each day in the dp array
8    for (let day = 1; day < lastDay; day++) {
9        // If the current day is among the travel days, we need to consider it for cost calculation
10        let costIfBuy1DayPass = days.includes(day) ? dp[day - 1] + cost1DayPass : dp[day - 1];
11        let costIfBuy7DayPass = (day > 7 ? dp[day - 7] : dp[0]) + cost7DayPass;
12        let costIfBuy30DayPass = (day > 30 ? dp[day - 30] : dp[0]) + cost30DayPass;
13
14        // The minimum cost up to the current day will be the least of the costs using any of the passes
15        dp[day] = Math.min(costIfBuy1DayPass, costIfBuy7DayPass, costIfBuy30DayPass);
16    }
17
18    // Return the minimum cost on the last day of travel
19    return dp[lastDay - 1];
20}
21

Time and Space Complexity

The provided Python code is designed to find the minimum cost of buying tickets for a set of travel days, and the solution involves dynamic programming with memoization (@cache) and binary search (bisect_left).

Time Complexity

The time complexity of the algorithm is primarily governed by the calls to the function dfs. This recursive function is enhanced with memoization, which ensures that each of the N days is processed only once. Inside dfs, a binary search is performed thrice (once for each ticket type) using Python's bisect_left. This takes O(log N) time for each call. Since memoization ensures that each day is processed only once and there are 3 choices for the type of ticket at each day, the number of times bisect_left is called is 3N.

Hence, the overall time complexity is O(N * 3 * log N), which can be simplified to O(N log N).

Space Complexity

The space complexity is determined by the storage required for memoization and the stack space used by recursive calls. The memoization (@cache) will store results for each of the N days, which gives us a space complexity of O(N) for memoization.

As for the recursion stack, in the worst case, the depth will be N (if every day is a travel day and we can buy a ticket for each single day), so the space complexity due to recursion is also O(N).

Thus, the total space complexity of the algorithm is O(N) (where the constants are ignored, and the larger term is considered).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know