Minimum Cost For Tickets

medium dynamic programming array

Problem

You travel on the days listed in days (1..365). Three passes cover travel: a 1-day pass costs costs[0], a 7-day pass costs costs[1] (covers the day bought plus the next 6 days), and a 30-day pass costs costs[2] (covers 30 consecutive days). Return the minimum total cost to cover every travel day.

Inputdays = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15]

Output11

Buy a 7-day pass on day 1 (covers 1–7, cost 7), a 1-day pass on day 8 (cost 2), and a 1-day pass on day 20 (cost 2). Total = 7 + 2 + 2 = 11.

days (comma-separated, 1..365)

costs [1d, 7d, 30d]

def mincost_tickets(days, costs):
    last = days[-1]
    travel = set(days)
    dp = [0] * (last + 1)
    for d in range(1, last + 1):
        if d not in travel:
            dp[d] = dp[d - 1]
        else:
            dp[d] = min(
                dp[d - 1] + costs[0],
                dp[max(0, d - 7)] + costs[1],
                dp[max(0, d - 30)] + costs[2],
            )
    return dp[last]

function mincostTickets(days, costs) {
  const last = days[days.length - 1];
  const travel = new Set(days);
  const dp = new Array(last + 1).fill(0);
  for (let d = 1; d <= last; d++) {
    if (!travel.has(d)) {
      dp[d] = dp[d - 1];
    } else {
      dp[d] = Math.min(
        dp[d - 1] + costs[0],
        dp[Math.max(0, d - 7)] + costs[1],
        dp[Math.max(0, d - 30)] + costs[2]
      );
    }
  }
  return dp[last];
}

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int last = days[days.length - 1];
        boolean[] travel = new boolean[last + 1];
        for (int d : days) travel[d] = true;
        int[] dp = new int[last + 1];
        for (int d = 1; d <= last; d++) {
            if (!travel[d]) {
                dp[d] = dp[d - 1];
            } else {
                dp[d] = Math.min(dp[d - 1] + costs[0],
                        Math.min(dp[Math.max(0, d - 7)] + costs[1],
                                 dp[Math.max(0, d - 30)] + costs[2]));
            }
        }
        return dp[last];
    }
}

int mincostTickets(vector<int>& days, vector<int>& costs) {
    int last = days.back();
    vector<bool> travel(last + 1, false);
    for (int d : days) travel[d] = true;
    vector<int> dp(last + 1, 0);
    for (int d = 1; d <= last; d++) {
        if (!travel[d]) {
            dp[d] = dp[d - 1];
        } else {
            dp[d] = min({ dp[d - 1] + costs[0],
                          dp[max(0, d - 7)] + costs[1],
                          dp[max(0, d - 30)] + costs[2] });
        }
    }
    return dp[last];
}

Explanation

You travel on certain days and can cover them with 1-day, 7-day, or 30-day passes. We walk forward through the calendar and, for each day, ask: what is the cheapest way to be covered up to here?

dp[d] is the minimum cost to cover all travel up to and including day d. If d is not a travel day, nothing new is needed, so dp[d] = dp[d-1].

If d is a travel day, we try the three passes and take the cheapest: a 1-day pass (dp[d-1] + costs[0]), a 7-day pass that started 7 days back (dp[d-7] + costs[1]), or a 30-day pass (dp[d-30] + costs[2]). The max(0, d-7) guard keeps us from indexing before day 0.

Example: days = [1,4,6,7,8,20], costs = [2,7,15]. A 7-day pass bought on day 1 covers days 1–7 for 7, then single-day passes on day 8 and day 20 cost 2 each, for a total of 11 at dp[20].

We fill one value per calendar day up to the last travel day W, each in constant time, so the work is O(W).

Time: O(W) where W is the last travel day Space: O(W)