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:
costs[0] dollars,costs[1] dollars, andcosts[2] dollars.The passes allow that many days of consecutive travel.
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 <= 3651 <= days[i] <= 365days is in strictly increasing order.costs.length == 31 <= costs[i] <= 1000Problem Overview: You are given a list of travel days and ticket costs for 1-day, 7-day, and 30-day passes. Each pass covers consecutive days starting from the purchase date. The goal is to choose passes so every travel day is covered while minimizing the total cost.
Approach 1: Recursive with Memoization (Top-Down DP) (Time: O(n), Space: O(n))
This approach treats the problem as a decision tree. For each travel day index i, you decide whether to buy a 1-day, 7-day, or 30-day pass. After choosing a pass, skip forward to the next uncovered travel day using iteration over the days array. A memoization table stores the minimum cost starting from index i, preventing repeated work. Each state is computed once, and the recursion explores three options per state.
The key insight: the optimal decision for day i only depends on the minimum cost of future travel days. Memoization converts the exponential brute-force recursion into linear time by caching results. This pattern is common in dynamic programming problems where decisions affect future states.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(n), Space: O(n))
The bottom-up version builds the answer iteratively. Define dp[i] as the minimum cost required to cover travel days starting from index i. Process the array from the end toward the beginning. For each index, compute three candidate costs: buy a 1-day pass and move to i+1, buy a 7-day pass and advance until the first day outside the 7-day window, or buy a 30-day pass and advance similarly.
Each step scans forward to locate the next uncovered travel day, then combines the ticket cost with the already-computed future cost. The recurrence becomes dp[i] = min(cost1 + dp[next1], cost7 + dp[next7], cost30 + dp[next30]). Since each travel day is processed once and the array is traversed sequentially, the total time stays linear.
The solution relies on simple iteration over an array and optimal substructure from dynamic programming. No complex data structures are required.
Recommended for interviews: The bottom-up dynamic programming approach is typically preferred. It demonstrates strong understanding of state transitions, avoids recursion overhead, and clearly shows how future costs influence current decisions. Explaining the recursive memoized version first helps show the progression from brute-force thinking to an optimized DP formulation.
This approach uses dynamic programming to maintain a cost array where each cell represents the minimum cost to travel up to that day. For each travel day, you decide to either buy a 1-day, 7-day, or 30-day pass and record the cost accordingly.
The C code initializes a dynamic programming (DP) array where each index represents the cost to travel up to that day. For each given travel day, it computes the minimum cost considering each type of pass (1-day, 7-day, 30-day) and stores the result in the DP array.
Time Complexity: O(n) where n is the last travel day. Space Complexity: O(n) for the DP array.
This approach uses recursion with memoization to explore each travel day recursively, storing intermediate results to avoid redundant calculations. It offers a top-down perspective on decision-making for ticket purchasing.
This C implementation uses recursive depth-first search (DFS) with memoization to explore and store results of subproblems, reducing redundant calculations. The function calculates the minimum cost by considering costs of possible travel passes starting at each travel day index.
Time Complexity: O(n) where n is the number of travel days due to memoization. Space Complexity: O(n) for the memo array.
We define a function dfs(i), which represents the minimum cost required from the i-th trip to the last trip. Thus, the answer is dfs(0).
The execution process of the function dfs(i) is as follows:
i geq n, it means all trips have ended, return 0;j of the next trip, then recursively call dfs(j), and finally return the minimum cost among these three purchasing methods.To avoid repeated calculations, we use memoization search to save the results that have already been calculated.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n represents the number of trips.
Python
Java
C++
Go
TypeScript
Let's denote the last day in the days array as m. We can define an array f of length m + 1, where f[i] represents the minimum cost from day 1 to day i.
We can calculate the value of f[i] in increasing order of the dates in the days array, starting from day 1. If day i is a travel day, we can consider three purchasing options: buying a 1-day pass, buying a 7-day pass, and buying a 30-day pass. We calculate the cost for these three purchasing methods separately and take the minimum cost among these three as the value of f[i]. If day i is not a travel day, then f[i] = f[i - 1].
The final answer is f[m].
The time complexity is O(m), and the space complexity is O(m). Here, m represents the last day of travel.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) where n is the last travel day. Space Complexity: O(n) for the DP array. |
| Recursive with Memoization Approach | Time Complexity: O(n) where n is the number of travel days due to memoization. Space Complexity: O(n) for the memo array. |
| Memoization Search + Binary Search | — |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n) | O(n) | When deriving the solution from a recursive decision tree and converting it to DP |
| Bottom-Up Dynamic Programming | O(n) | O(n) | Preferred interview solution with iterative state transitions and no recursion overhead |
Minimum Cost for Tickets - Dynamic Programming - Leetcode 983 - Python • NeetCode • 84,980 views views
Watch 9 more video solutions →Practice Minimum Cost For Tickets with our built-in code editor and test cases.
Practice on FleetCode