AlgoMaster Logo

Minimum Cost For Tickets

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

A greedy rule like "always pick the cheapest per-day option" fails here. A 7-day pass costing $7 is cheaper than buying seven $2 one-day passes ($14) if you travel every day that week, but only if enough travel days fall inside the window to justify it. The optimal choice on any given travel day depends on how the future travel days are spaced.

The decision for each travel day, buy a 1-day, 7-day, or 30-day pass, cannot be made in isolation. It depends on how many upcoming travel days fall within the pass window, and those windows overlap. Overlapping subproblems with an optimal-substructure choice at each step point to dynamic programming.

Key Constraints:

  • 1 <= days[i] <= 365 → The whole calendar fits in one year, so a DP indexed by calendar day needs an array of size at most 366.
  • 1 <= days.length <= 365 → At most 365 travel days, so an O(n^2) solution stays under 135,000 operations and is fast enough. An O(D) calendar-day DP is also viable.
  • days is strictly increasing → No duplicates and already sorted, so no preprocessing is needed.
  • 1 <= costs[i] <= 1000 → Costs are small positive integers. The maximum total cost is bounded by 365 * 1000, which fits comfortably in a 32-bit int, so there is no overflow concern.

Approach 1: Brute Force (Recursion)

Intuition

At each travel day there are three choices: buy a 1-day pass, a 7-day pass, or a 30-day pass. Each pass covers a different range of future days, so after buying one, the next decision is made at the first travel day the pass does not cover.

This gives a recursive structure. Starting from the first travel day, try all three pass types, recursively solve the remaining days, and return the minimum total cost. Because every travel day must be covered by some pass and we try every pass at every position, the recursion explores all valid ways to cover the schedule and the minimum over all of them is the answer.

Algorithm

  1. Define a recursive function solve(idx) that returns the minimum cost to cover travel from days[idx] onward.
  2. Base case: if idx >= days.length, return 0 (no more travel days to cover).
  3. For each pass type (1-day, 7-day, 30-day), find the next travel day index that is NOT covered by this pass. The cost of this choice is costs[passType] + solve(nextIdx).
  4. Return the minimum of the three choices.

Visualization and Code

Loading animation...

The recursion recomputes the same subproblems many times. For example, solve(4) can be reached from several different earlier choices, and each time it recomputes the same value. Caching the result of solve(idx) the first time it is computed removes that redundant work.

Approach 2: Memoization (Top-Down DP)

Intuition

The recursive solution has overlapping subproblems. The function solve(idx) only depends on idx, and there are at most n unique values of idx. If we store the result of each solve(idx) in a memo table after computing it the first time, we eliminate all redundant work.

Algorithm

  1. Create a memo array of size n, initialized to -1 (uncomputed).
  2. Define solve(idx) as before, but before computing, check if memo[idx] is already filled. If so, return it directly.
  3. After computing the result for idx, store it in memo[idx].
  4. Return solve(0).

Visualization and Code

Loading animation...

The forward scans to find the next uncovered day are what push each subproblem to O(n) and the total to O(n^2). Indexing the DP by calendar day instead of by travel-day index removes those scans, since a pass that starts on day d always ends on a fixed day (d+6 or d+29), so the lookback offset is a constant.

Approach 3: Bottom-Up DP (Calendar Days)

Intuition

Instead of working forward from each travel day, define dp[d] as the minimum cost to cover all travel from day 1 through day d. On any day d:

  • If day d is NOT a travel day, dp[d] = dp[d-1], since nothing new needs covering.
  • If day d IS a travel day, dp[d] = min(costs[0] + dp[d-1], costs[1] + dp[max(0, d-7)], costs[2] + dp[max(0, d-30)]).

The travel-day case considers the three passes that could cover day d. A 1-day pass covers only day d, leaving days 1 through d-1 to be paid for, which costs dp[d-1]. A 7-day pass that includes day d can start as early as day d-6, covering days d-6 through d, so everything before day d-6 still needs covering: that prefix cost is dp[d-7]. The 30-day case is the same with a 29-day reach back, giving dp[d-30]. Using max(0, d-k) clamps the lookback so early days read dp[0] = 0. Each transition is O(1), and the loop runs once per calendar day up to the last travel day, so the DP runs in O(D) time.

Algorithm

  1. Mark every day in the days array as a travel day for O(1) lookup (a boolean array indexed by day, or a hash set).
  2. Create a dp array of size lastDay + 1, with dp[0] = 0.
  3. For each day d from 1 to lastDay: if d is not a travel day, dp[d] = dp[d-1]. Otherwise, set dp[d] to the minimum of the three pass options.
  4. Return dp[lastDay].

Visualization and Code

Loading animation...