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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MincostTickets(int[] days, int[] costs) {
6 var travelDays = new HashSet<int>(days);
7 int[] dp = new int[366];
8 for (int i = 1; i <= 365; i++) {
9 if (!travelDays.Contains(i)) {
10 dp[i] = dp[i - 1];
11 } else {
12 dp[i] = Math.Min(
13 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 }
19 return dp[365];
20 }
21}The C# solution mirrors the logic seen in Python and Java, utilizing HashSet for efficient travel day checks and structuring the DP array to accumulate the minimum cost to each successive 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
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.