Problem 42.7 · Pattern Recognition DrillsMedium

Minimum Cost For Tickets

What it teaches:

Practise it on judges as “Minimum Cost For Tickets”.

In plain words

Go through the calendar day by day and write down the cheapest way to cover all your trips up to that day. On a day you don't travel, the cost is the same as yesterday. On a travel day, today's pass ends a 1-day, 7-day or 30-day pass: take the cheapest of yesterday's cost + 1-day price, the cost from 7 days ago + 7-day price, and the cost from 30 days ago + 30-day price.

Return the minimum total cost. Example: days = [1,4,6,7,8,20], costs = [2,7,15] → 11.

The problem

You travel on the given increasing days (1–365). Passes cost costs[0] (1 day), costs[1] (7 days), costs[2] (30 days). Return the minimum total cost.

Example 1

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11

Constraints

1 ≤ days ≤ 365

Pattern clues in the wording

→ Minimum cost over overlapping choices
→ Small day range

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	days = [1,4,6,7,8,20] costs = [2,7,15]	11
2	days = [1,2,3,4,5,6,7,8,9,10,30,31] costs = [2,7,15]	17

From slow to fast

Approaches

1. DP over calendar days · O(365)

DP over calendar days

Time O(365) Space O(365)

dp[d] = dp[d − 1] if not travelling; otherwise min(dp[d − 1] + c0, dp[d − 7] + c1, dp[d − 30] + c2) with negative indices as 0.

▶ Dry run: Cheapest cost up to each daydays = [1,4,6,7,8,20], costs = [2,7,15]

9–19

Step 1/5dp[0] = 0. Day 1 is a travel day: a 1-day pass (2) beats 7 and 15, so dp[1] = 2.

Approach 1

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]; continue; }
            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];
    }
}

Verdict: Tiny state space.

Before you submit

Edge cases and common mistakes

Test these inputs

One travel day
A 1-day pass more expensive than a 7-day pass

Mistakes people make

Choosing passes greedily by cost per day.

Interview

Follow-up questions

What clue says DP rather than greedy?

Command Palette

The problem

Approaches

DP over calendar days

Edge cases and common mistakes

Follow-up questions