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.
1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5 public int mincostTickets(int[] days, int[] costs) {
6 Set<Integer> daySet = new HashSet<>();
7 for (int day : days) daySet.add(day);
8 int[] dp = new int[366];
9 for (int i = 1; i < 366; i++) {
10 if (!daySet.contains(i)) {
11 dp[i] = dp[i - 1];
12 } else {
13 dp[i] = Math.min(dp[i - 1] + costs[0],
14 Math.min(dp[Math.max(0, i - 7)] + costs[1],
15 dp[Math.max(0, i - 30)] + costs[2]));
16 }
17 }
18 return dp[365];
19 }
20}In the Java solution, a HashSet is used to determine travel days quickly. The DP array covers all 365 days, calculating costs on travel days and carrying over previous costs on non-travel days.
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
The Java implementation applies recursive calls enhanced with memoization to calculate the minimum ticket costs. It maintains a memo array for previously computed results, seeking to minimize the aggregate price by evaluating each travel pass option at each day point recursively.