Sponsored
Sponsored
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.
Time Complexity: O(n) where n is the last travel day. Space Complexity: O(n) for the DP array.
1def mincostTickets(days, costs):
2 travel_days = set(days)
3 dp = [0] * (days[-1] + 1)
4 for i in range(1, days[-1] + 1):
5 if i not in travel_days:
6 dp[i] = dp[i - 1]
7 else:
8 dp[i] = min(dp[i - 1] + costs[0],
9 dp[i - 7] + costs[1] if i >= 7 else costs[1],
10 dp[i - 30] + costs[2] if i >= 30 else costs[2])
11 return dp[-1]
12
13# Example Usage
14print(mincostTickets([1,4,6,7,8,20], [2,7,15])) # Output: 11Python follows a similar approach as the other implementations, using a set to quickly identify travel days. The dynamic programming array holds the cumulative cost to travel up to the current day.
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.
Time Complexity: O(n) where n is the number of travel days due to memoization. Space Complexity: O(n) for the memo array.
1
This Python variant employs recursion combined with memoization for storing intermediate solutions, intending to calculate and conserve the minimum cost of tickets. The recursive helper investigates each travel day to determine which combination of passes yields the least expense.