Minimum Cost For Tickets

Medium Dynamic Programming 1D DP Original on LeetCode

Reported atZeptoGroww

Minimum Cost For Tickets is a medium dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (dp over calendar days), runs in O(D) time and O(D) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try all three passes recursively) up.

Problem

You plan to travel by train on certain days of one year, given as the strictly increasing array days (each between 1 and 365). Three kinds of passes are sold:

  • a 1-day pass for costs[0],
  • a 7-day pass for costs[1],
  • a 30-day pass for costs[2].

A pass bought for day d covers that many consecutive days starting at d (a 7-day pass bought on day 4 covers days 4 through 10). Return the minimum total amount needed to cover every travel day.

Examples

Example 1

Input
days = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15]
Output
11
Why
Buy 1-day passes for days 1 and 20, and a 7-day pass on day 4 that covers days 4 through 10: 2 + 7 + 2 = 11.

Example 2

Input
days = [1, 2, 3, 4, 5, 6, 7, 20], costs = [4, 9, 50]
Output
13
Why
One 7-day pass covers days 1 to 7 for 9, and a 1-day pass covers day 20 for 4.

Constraints

  • 1 <= days.length <= 365
  • 1 <= days[i] <= 365, and days is strictly increasing.
  • costs.length == 3
  • 1 <= costs[i] <= 1000

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try all three passes recursively)O(3^n)O(n)
Optimal (DP over calendar days)O(D)O(D)

1Brute force (try all three passes recursively)

TimeO(3^n)Each call branches three ways until the days run out.
SpaceO(n)The recursion stack is at most n deep.

Start at the first travel day that is not yet covered. Buy one of the three passes, skip every travel day it covers, and recurse on the rest. Return the cheapest of the three branches. Without remembering results, the same suffixes are solved again and again.

  1. solve(i) = 0 if i == days.length.
  2. For each pass (length 1, 7 or 30): find the first j with days[j] >= days[i] + length.
  3. solve(i) = min over the passes of cost + solve(j).
class Solution {
    private static final int[] LEN = { 1, 7, 30 };

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

    private int solve(int[] days, int[] costs, int i) {
        if (i == days.length) return 0;
        int best = Integer.MAX_VALUE;
        for (int p = 0; p < 3; p++) {
            int j = i;
            while (j < days.length && days[j] < days[i] + LEN[p]) j++;
            best = Math.min(best, costs[p] + solve(days, costs, j));
        }
        return best;
    }
}

2Optimal (DP over calendar days)

TimeO(D)D is the last travel day (at most 365); each day is processed in O(1).
SpaceO(D)The dp array and the travel-day flags have D + 1 entries.

Walk through the calendar from day 1 to the last travel day. dp[d] is the cheapest cost that covers every travel day up to d. A non-travel day adds nothing. On a travel day, the pass covering it was bought 1, 7 or 30 days back at the latest, so take the cheapest of those three options.

  1. last = days[n - 1]; mark the travel days in a boolean array.
  2. dp[0] = 0. For d from 1 to last: if d is not a travel day, dp[d] = dp[d - 1].
  3. Otherwise dp[d] = min(dp[d - 1] + costs[0], dp[max(0, d - 7)] + costs[1], dp[max(0, d - 30)] + costs[2]).
  4. 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];
                continue;
            }
            int one = dp[d - 1] + costs[0];
            int week = dp[Math.max(0, d - 7)] + costs[1];
            int month = dp[Math.max(0, d - 30)] + costs[2];
            dp[d] = Math.min(one, Math.min(week, month));
        }
        return dp[last];
    }
}

Edge cases to test

  • A single travel day
  • A longer pass that is cheaper than a shorter one
  • Travel days spread far apart, so only 1-day passes make sense
  • Travel on every day of the year

Hints

Hint 1

On the first uncovered travel day you must buy some pass. Which three choices do you have, and what is left afterwards?

Hint 2

Let dp[d] be the cheapest way to cover every travel day up to day d. A day you do not travel costs nothing extra: dp[d] = dp[d - 1].

Hint 3

On a travel day, dp[d] = min(dp[d - 1] + costs[0], dp[d - 7] + costs[1], dp[d - 30] + costs[2]), treating negative indices as 0.

FAQ

What is the best time complexity for Minimum Cost For Tickets?

Optimal (DP over calendar days) runs in O(D) time and O(D) extra space. D is the last travel day (at most 365); each day is processed in O(1).

Which pattern does Minimum Cost For Tickets use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Minimum Cost For Tickets?

Yes. Brute force (try all three passes recursively) takes O(3^n) time and O(n) space. Start at the first travel day that is not yet covered.

Which edge cases should I test for Minimum Cost For Tickets?

A single travel day; A longer pass that is cheaper than a shorter one; Travel days spread far apart, so only 1-day passes make sense; Travel on every day of the year.