Minimum cost for tickets

983.Minimum Cost for Tickets

Dynamic Programming

Problem Statement:

You are given an array days, where each element represents a day you need to travel, and an array costs, where:

• costs[0] is the cost of a 1-day pass.
• costs[1] is the cost of a 7-day pass.
• costs[2] is the cost of a 30-day pass.

Return the minimum cost needed to cover all travel days using any combination of these passes.

Algorithm:

1. Create a boolean array isTravelDay to mark the days that are travel days.
2. Use a dynamic programming array dp, where dp[i] represents the minimum cost to cover up to day i.
3. For each day:
   • If it is not a travel day, set dp[i] = dp[i - 1].
   • If it is a travel day, calculate the cost using:
     • A 1-day pass: dp[i - 1] + costs[0].
     • A 7-day pass: dp[i - 7] + costs[1].
     • A 30-day pass: dp[i - 30] + costs[2].
4. Return dp[365] as the minimum cost to cover all travel days.

Complexity:

Time: O(365), as we iterate over all days in a year. | Space: O(365), for the dp and isTravelDay arrays.

Java Implementation:

public int mincostTickets(int[] days, int[] costs) {
    boolean[] isTravelDay = new boolean[366];
    for (int day : days) isTravelDay[day] = true; // Mark travel days

    int[] dp = new int[366]; // dp[i] = minimum cost to cover up to day i
    for (int i = 1; i < 366; i++) {
        if (!isTravelDay[i]) {
            dp[i] = dp[i - 1]; // If not a travel day, cost remains same as previous day
            continue;
        }
        dp[i] = Integer.MAX_VALUE;
        dp[i] = Math.min(dp[i], dp[Math.max(0, i - 1)] + costs[0]); // 1-day pass
        dp[i] = Math.min(dp[i], dp[Math.max(0, i - 7)] + costs[1]); // 7-day pass
        dp[i] = Math.min(dp[i], dp[Math.max(0, i - 30)] + costs[2]); // 30-day pass
    }
    return dp[365]; // Return the total minimum cost for the year
}
                

Python Implementation:

def mincostTickets(days, costs):
    is_travel_day = [False] * 366
    for day in days:
        is_travel_day[day] = True

    dp = [0] * 366  # dp[i] = minimum cost to cover up to day i
    for i in range(1, 366):
        if not is_travel_day[i]:
            dp[i] = dp[i - 1]  # No cost change if not a travel day
            continue
        dp[i] = min(
            dp[max(0, i - 1)] + costs[0],  # 1-day pass
            dp[max(0, i - 7)] + costs[1],  # 7-day pass
            dp[max(0, i - 30)] + costs[2], # 30-day pass
        )
    return dp[365]
                

C++ Implementation:

int mincostTickets(vector& days, vector& costs) {
    vector isTravelDay(366, false);
    for (int day : days) isTravelDay[day] = true; // Mark travel days

    vector dp(366, 0); // dp[i] = minimum cost to cover up to day i
    for (int i = 1; i < 366; ++i) {
        if (!isTravelDay[i]) {
            dp[i] = dp[i - 1]; // No cost change if not a travel day
            continue;
        }
        dp[i] = min({
            dp[max(0, i - 1)] + costs[0], // 1-day pass
            dp[max(0, i - 7)] + costs[1], // 7-day pass
            dp[max(0, i - 30)] + costs[2] // 30-day pass
        });
    }
    return dp[365];
}