983. Minimum Cost For Tickets - Detailed Explanation

Problem Statement

You are given an array days (strictly increasing) which lists the days of the year you will travel, and an array costs of length 3 where:

• costs[0] is the price of a 1-day pass,
• costs[1] is the price of a 7-day pass,
• costs[2] is the price of a 30-day pass.

A pass covers a consecutive range of days starting on the day you use it. For example, if you use a 7-day pass on day 2, it covers days 2 through 8 (inclusive). Your goal is to travel on all the days in the days list while spending the minimum amount on tickets.

Example 1:

• Input: days = [1,4,6,7,8,20], costs = [2,7,15]
• Output: 11
• Explanation: One optimal solution is:
  • On day 1, buy a 1-day pass for $2 (covers day 1).
  • On day 3, buy a 7-day pass for $7 (covers days 3,4,...,9).
  • On day 20, buy a 1-day pass for 2 (covers day 20). In total you spend 11 and cover all travel days.

Example 2:

• Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
• Output: 17
• Explanation: One optimal solution is:
  • On day 1, buy a 30-day pass for $15 (covers days 1–30).
  • On day 31, buy a 1-day pass for 2 (covers day 31). In total you spend 17 and cover all travel days.

What’s being asked: Find the minimum cost to cover all given travel days with these passes. We need to choose wisely among 1-day, 7-day, or 30-day tickets for each segment of travel so that all days in days are covered at minimal total cost. This is a classic optimization problem that can be solved with dynamic programming, as each decision (which pass to buy) affects future days and has overlapping subproblems.

Hints to Guide the Solution

• Think in terms of decisions: For each travel day, you have a decision to make – buy a 1-day, 7-day, or 30-day pass on that day. Each choice will cover that day (and possibly days after it) and incur a certain cost.

• Recursive intuition: Consider the first travel day. If you buy a 1-day pass, you cover only that day and then need to solve the subproblem for the remaining days. If you buy a 7-day pass, you cover up to 7 days starting from that day, skipping the need for tickets for those days, and then solve the subproblem for the first travel day after that window. Similarly for a 30-day pass. This hints at a recursive structure: the problem can be broken into the cost for the first segment plus the cost for the rest.

• Overlapping subproblems: Many day ranges will overlap. For instance, whether you buy a 7-day pass on day 3 or on day 4, the cost to cover days after day 9 might end up being the same subproblem. This means the naive recursion will repeat a lot of calculations for overlapping intervals. Caching (memoization) or dynamic programming will be needed to avoid recomputation.

• DP state definition: Try to define a state that represents “the minimum cost to cover travel from a certain starting point or up to a certain day.” For example, define dp[i] as the minimum cost to cover all travel days from day 1 up to day i, or alternatively define a state that progresses through the list of travel days. Identifying the right state and recurrence is key.

• Use the constraints: The days are between 1 and 365. This is a small range (at most one year), which means a dynamic programming solution that iterates through each day of the year (365 days) is feasible. You don’t necessarily need to simulate every day if you jump between travel days, but knowing the maximum range (365) can simplify your approach without worrying about large time complexity.

Brute Force Approach (Naive Recursive)

A straightforward approach is to try all possible combinations of tickets for covering the travel days. This can be done with recursion/backtracking: on each travel day, choose one of the three pass types and recursively solve for the remaining days that aren’t covered by that pass. The base case is when all travel days are covered. This brute force will explore every decision tree:

• Recursive strategy: Start from the first travel day in the list. At that day, consider three possibilities: buy a 1-day pass, a 7-day pass, or a 30-day pass. Each choice incurs a cost and covers a certain range of subsequent days. Skip all covered days and recursively solve for the next travel day that isn’t covered yet. Compute the total cost for each choice and take the minimum.
• Exponential complexity: The brute force approach tries every combination of buying/not buying passes and has no pruning of subproblems. In the worst case (e.g., if you travel nearly every day), at each day you have up to 3 choices, leading to roughly 3^N possibilities for N travel days. This is an exponential time algorithm. For example, with N=365 (travel every day), 3^365 combinations is astronomically large.
• Why it’s inefficient: There is significant overlap in subproblems. For instance, suppose on day 1 you try a 7-day pass covering days 1–7, and separately you try a 1-day pass on day 1 then another pass later. Both scenarios will eventually require solving the subproblem for days 8 onwards. The brute force will solve the “from day 8 to end” subproblem multiple times independently, wasting time. Without caching, the same computations are repeated over and over.
• Conclusion: A naive recursion will time out except for very small inputs. It’s a good conceptual starting point to understand the decision space, but we need to optimize it by eliminating repeated work.

Optimized Approaches

To make the solution efficient, we use dynamic programming to avoid recomputation of overlapping subproblems. There are two main DP strategies here: top-down (recursion with memoization) and bottom-up (iterative). We’ll also discuss a space optimization (sliding window) that takes advantage of the problem’s limited range of 30 days for looking back.

Recursion + Memoization (Top-Down DP)

This approach refines the brute force by storing results of subproblems so we don't solve them repeatedly. We use a recursive function that computes the minimum cost starting from a given index in the days list, and we memoize (cache) the results for each index.

• Define subproblem: Let dfs(i) be the minimum cost to cover travel days from days[i] to the end of the list. We want to compute dfs(0), the cost starting at the first day.

• Recurrence (choices at days[i]): At the i-th travel day, we have three options:

  1. 1-day pass: Pay costs[0] and cover just days[i]. Then the next day to consider will be i+1 (next travel day).
  2. 7-day pass: Pay costs[1] and cover days[i] and as many subsequent travel days as fall within the next 6 days after days[i]. We need to find the index j such that days[j] is the first day > days[i] + 6 (meaning day days[i] + 7 is not covered). Then dfs(i) can skip directly to dfs(j) after using a 7-day pass.
  3. 30-day pass: Similarly, pay costs[2] and cover days[i] and all travel days within 29 days after it. Find index k for the first travel day > days[i] + 29, and skip to dfs(k).

• Memoization: Use a dictionary or array to store results for dfs(i) once computed. If we call dfs(i) again, just return the stored result instead of recomputing. This cuts down the complexity drastically – each index (subproblem) is solved once.

• Pseudocode:

  dfs(i): 
      if i >= len(days): return 0 
      if i in memo: return memo[i] 
      // option1: one-day pass 
      cost1 = costs[0] + dfs(i+1) 
      // option2: seven-day pass 
      j = first index >= i where days[j] > days[i] + 6 
      cost2 = costs[1] + dfs(j) 
      // option3: thirty-day pass 
      k = first index >= i where days[k] > days[i] + 29 
      cost3 = costs[2] + dfs(k) 
      memo[i] = min(cost1, cost2, cost3) 
      return memo[i] 
  

  This will explore each state (each value of i) once, comparing three options each time. Finding the index j and k can be done with a loop or binary search since days is sorted.

• Complexity: With memoization, the time complexity is O(N) where N is the number of travel days (up to 365), because each index i from 0 to N-1 is solved once. Each state does O(1) work (just a few comparisons plus the index search for j and k, which can be optimized to O(log N) with binary search or O(1) with two pointers). The space complexity is O(N) for the recursion stack and memo table. In our scenario N ≤ 365, so this is very efficient.

• Example walkthrough: Using Example 1 (days=[1,4,6,7,8,20]):

  • dfs(0) (day 1) will consider:
    • 1-day pass: cost 2 + dfs(1) for day 4…
    • 7-day pass: cost 7 + dfs(j) where days[j] is first > 1+6=7 (so j at day 8)…
    • 30-day pass: cost 15 + dfs(k) where days[k] is first > 1+29=30 (so k at day 20)…
  • These lead to recursive calls dfs(1), dfs(3), dfs(5) (if we number indices 0-based). Each of those will similarly evaluate 3 choices. With memoization, each dfs(i) is computed once. In the end, dfs(0) gets the minimum cost which would be 11 for this example.

Bottom-Up Dynamic Programming (Iterative)

In a bottom-up approach, we build the solution by solving smaller subproblems first and using those to solve larger ones. There are multiple ways to formulate the DP, but two common ones are:

1. DP by day (calendar DP): Use an array dp[0..365] (if 365 is the last day, or up to days[-1]) where dp[d] represents the minimum cost to cover all travel days up to day d. We initialize dp[0] = 0 (no cost for day 0). Then for each day from 1 to 365:

   • If it’s not a travel day, no new ticket is needed: dp[d] = dp[d-1].
   • If it is a travel day, compute:

     dp[d] = min( dp[d-1] + costs[0],  
                  dp[max(0, d-7)] + costs[1],  
                  dp[max(0, d-30)] + costs[2] ) 
     

     Here dp[max(0, d-7)] is the cost up to 7 days before (or 0 if out of range) plus a 7-day pass covering day d, and similarly for 30 days. We take the minimum of the three options.
   • We only consider buying a pass on actual travel days (if it’s not a travel day, we carry over the previous cost). Using a set or boolean array of travel days helps to check this quickly.
   • After iterating through all days, the answer will be dp[last_day] (where last_day = days[-1]).

   This approach ensures we evaluate costs at each possible day, including days that are not in the travel list (which just copy the previous cost). It works within the 365-day limit comfortably.

2. DP by index of travel days: Another formulation is to have dp[i] represent the minimum cost to cover travel up to the i-th travel day (i.e., days[0..i]). We can iterate over the list of travel days. For each travel day days[i], we consider buying each type of pass ending on that day:

   • Find the index a of the first travel day that is outside the 1-day pass covering days[i] (which is just i itself for 1-day). So a = i+1.

   • Find index b of the first travel day > days[i] + 6 (outside the 7-day window).

   • Find index c of the first travel day > days[i] + 29 (outside the 30-day window).

   • Then:

     dp[i] = min( costs[0] + dp[a-1],  
                  costs[1] + dp[b-1],  
                  costs[2] + dp[c-1] ) 
     

     Here we treat dp[-1] = 0 as base (cost before any travel day). Essentially, if we buy a 7-day pass on day days[i], we add its cost to the cost up to the last travel day before the coverage started. We can find b-1 by looking backwards or using two pointers to move b forward as i increases.

   • We compute dp in increasing order of i. The answer will be dp[n-1] for n travel days.

   This method only iterates through the travel days, not every calendar day, so it can be more efficient if days is much smaller than 365. In our problem constraints, N can be at most 365 anyway, so both approaches are similar in complexity.

• Bottom-up example (calendar days): Using Example 1, we initialize dp[0]=0. Then:

  • Day 1: travel day,
    dp[1] = min(dp[0]+2, dp[0]+7, dp[0]+15) = 2 (buy 1-day pass) .

  • Days 2–3: not travel days, so dp[2]=dp[1]=2, dp[3]=dp[2]=2.

  • Day 4: travel day,
    dp[4] = min(dp[3]+2, dp[0]+7, dp[0]+15) = min(4, 7, 15) = 4. (Cheapest is two 1-day passes on days 1 and 4, totaling $4 so far.)

  • Day 5: not travel, dp[5]=dp[4]=4.

  • Day 6: travel day,
    dp[6] = min(dp[5]+2, dp[0]+7, dp[0]+15) = min(6, 7, 15) = 6. (Now cost $6, using three 1-day passes on 1,4,6.)

  • Day 7: travel day,
    dp[7] = min(dp[6]+2, dp[0]+7, dp[0]+15) = min(8, 7, 15) = 7. (Buying a 7-day pass covering days 1–7 for 7 becomes better than 1-day passes, so the total cost drops to 7.)

  • Day 8: travel day,
    dp[8] = min(dp[7]+2, dp[1]+7, dp[0]+15) = min(9, 2+7, 15) = 9. (Cost 9: the optimal now is the 7 pass (covering days 1–7) + a $2 pass for day 8.)

  • Days 9–19: no travel, cost stays $9 (carry over dp[8]).

  • Day 20: travel day,
    dp[20] = min(dp[19]+2, dp[13]+7, dp[0]+15) = min(9+2, 9+7, 15) = 11. (The best is 9 up to day 19 plus a 1-day pass for day 20, totaling 11.)

  • Result: dp[20] = 11. This matches the expected answer. Notice how the optimal strategy dynamically changed: initially individual passes, then a 7-day pass covered a bunch of days cheaply, then individual passes later. The DP calculated this optimally.

• Correctness: This DP works because of optimal substructure – the optimal way to cover up to day d is determined by the optimal costs up to previous days plus the cost of a new pass covering day d. We consider all pass types and trust the smaller subproblem solutions are optimal. The transition ensures we cover day d in whichever way is cheapest.

• Complexity: We either iterate up to day 365 (which is 365 iterations, constant time), or iterate through each travel day (at most 365) – either way O(365) = O(1) in big-O, or O(N) if N is number of travel days. Each day we do O(1) work checking three options, so it’s very fast. Space is O(366) ≈ O(1) for the DP array in the calendar-day approach, or O(N) for the travel-days DP. Typically, we say time O(N) and space O(N) for general N days, but with N ≤ 365 it's effectively bounded.

Sliding Window Optimization (Space and Time Optimization)

The above DP solutions are already efficient. We can optimize further in two ways: by avoiding iterating over days that aren’t in days (time optimization) and by using a rolling window for the DP array (space optimization). These optimizations are sometimes referred to as using a sliding window, because we only keep recent computations relevant to the next steps.

• Iterate over travel days only: The second DP method already does this. Instead of looping through every day of the year, you jump from one travel day to the next. To get the cost of 7 days ago or 30 days ago, you can use two pointers or binary search on the days list. For example, as you iterate through days, maintain a pointer j that moves to find the first day that is more than 6 days behind the current day (for the weekly pass), and another pointer k for 30 days behind. These pointers only move forward. This way, for each travel day, you determine where the coverage of a 7-day or 30-day pass starting on that day would end, without scanning from scratch. In terms of complexity, this keeps it O(N) but avoids the overhead of iterating on non-travel days. (In our problem N is at most 365, but if the year range were larger and travel days sparse, this would be a big win.)

• Rolling window for DP array: In the calendar-day DP, notice that to compute dp[d], we only ever look back at most 30 days (for dp[d-30]). Any day further in the past than 30 days doesn’t directly affect today’s decision because a 30-day pass is the longest duration. This means we don’t need to keep the full DP array of length 365 in memory – we can maintain a window of the last 30 (or 31) days and reuse it in a circular fashion. For example, we can use an array dp[31] and index it by day mod 31. When we move from day d to d+1, we overwrite the entry that is 31 days older than d+1, since it will no longer be needed. This saves space (though in this problem saving space from 365 integers is not critical, it’s the concept that matters).

• Memory optimization example: In the Programmer Coach solution, they used dp[i % 31] to reuse a length-31 array for the DP . When i advances, dp[i % 31] is effectively dp[i] while overwriting the value from dp[i-31] (which is no longer needed). The transitions use modulo arithmetic: for a given day d:

  dp[d % 31] = min( dp[(d-1) % 31] + costs[0],  
                    dp[max(0, d-7) % 31] + costs[1],  
                    dp[max(0, d-30) % 31] + costs[2] ) 
  

  This yields the same result as before, but uses O(31) space (constant).

• Overall optimized complexity: Time is O(N) and space O(1) with these optimizations. Given N ≤ 365, our earlier solution was already effectively O(1), but these techniques are useful in scenarios with larger ranges or when memory is at a premium. They demonstrate that we only need to keep a sliding window of 30 days of state to compute the next result.

Code Implementations

Python Implementation