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.
1using System.Collections.Generic;
public class Solution {
private int[] days;
private int[] costs;
private int[] memo;
public int MincostTickets(int[] days, int[] costs) {
this.days = days;
this.costs = costs;
this.memo = new int[days.Length];
Array.Fill(memo, -1);
return Dfs(0);
}
private int Dfs(int i) {
if (i >= days.Length) return 0;
if (memo[i] != -1) return memo[i];
int oneDay = costs[0] + Dfs(i + 1);
int j = i;
while (j < days.Length && days[j] < days[i] + 7) j++;
int sevenDay = costs[1] + Dfs(j);
while (j < days.Length && days[j] < days[i] + 30) j++;
int thirtyDay = costs[2] + Dfs(j);
return memo[i] = Math.Min(oneDay, Math.Min(sevenDay, thirtyDay));
}
}C# implements the same recursive logic with memoization as seen in other languages, preserving previously computed costs for successive travel days for faster computations. It methodically examines each day to be covered by these various ticket options.