We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost For Tickets

Difficulty: Medium

Problem Description

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: a 1-day pass, a 7-day pass, and a 30-day pass. Each pass allows for consecutive travel days. Return the minimum number of dollars you need to travel every day in the given list of days.

Key Insights

  • The problem can be approached using dynamic programming to find the minimum cost for each travel day.
  • We need to consider three different ticket options and their respective costs.
  • By maintaining a DP array where each index represents the minimum cost up to that day, we can build our solution iteratively.
  • The travel days are strictly increasing, which allows for efficient calculation without backtracking.

Space and Time Complexity

Time Complexity: O(n), where n is the number of travel days, since we iterate through the days array once. Space Complexity: O(n), for the DP array that stores the minimum cost up to each day.

Solution

To solve the problem, we use a dynamic programming approach. We will maintain an array dp where dp[i] represents the minimum cost to cover all travel days up to the i-th travel day. For each travel day, we will calculate the cost of each type of ticket (1-day, 7-day, and 30-day) and choose the minimum cost among them. The costs will be derived based on previously calculated values in the dp array.

Code Solutions

def mincostTickets(days, costs):
    dp = [0] * 366  # Create a DP array for days 0 to 365
    day_set = set(days)  # Use a set for quick lookup of travel days
    
    for i in range(1, 366):
        if i not in day_set:
            dp[i] = dp[i - 1]  # No travel on this day, cost remains the same
        else:
            # Calculate costs for each pass
            cost1 = dp[i - 1] + costs[0]  # 1-day pass
            cost7 = dp[max(0, i - 7)] + costs[1]  # 7-day pass
            cost30 = dp[max(0, i - 30)] + costs[2]  # 30-day pass
            dp[i] = min(cost1, cost7, cost30)  # Take the minimum cost

    return dp[365]  # Minimum cost to cover all travel days
← Back to All Questions