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] <= 1000This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of travel days due to memoization. Space Complexity: O(n) for the memo array.
| 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. |
Minimum Cost for Tickets - Dynamic Programming - Leetcode 983 - Python • NeetCode • 75,555 views views
Watch 9 more video solutions →Practice Minimum Cost For Tickets with our built-in code editor and test cases.
Practice on FleetCode