Minimum Cost For Tickets
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 <= 3651 <= days[i] <= 365, anddaysis strictly increasing.costs.length == 31 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(3^n)Each call branches three ways until the days run out.O(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.
- solve(i) = 0 if i == days.length.
- For each pass (length 1, 7 or 30): find the first j with days[j] >= days[i] + length.
- 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;
}
}class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
lengths = [1, 7, 30]
n = len(days)
def solve(i: int) -> int:
if i == n:
return 0
best = float("inf")
for p in range(3):
j = i
while j < n and days[j] < days[i] + lengths[p]:
j += 1
best = min(best, costs[p] + solve(j))
return best
return solve(0)class Solution {
int solve(const vector<int>& days, const vector<int>& costs, int i) {
static const int LEN[3] = {1, 7, 30};
if (i == (int)days.size()) return 0;
int best = INT_MAX;
for (int p = 0; p < 3; p++) {
int j = i;
while (j < (int)days.size() && days[j] < days[i] + LEN[p]) j++;
best = min(best, costs[p] + solve(days, costs, j));
}
return best;
}
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
return solve(days, costs, 0);
}
};function mincostTickets(days, costs) {
const LEN = [1, 7, 30];
const n = days.length;
const solve = (i) => {
if (i === n) return 0;
let best = Infinity;
for (let p = 0; p < 3; p++) {
let j = i;
while (j < n && days[j] < days[i] + LEN[p]) j++;
best = Math.min(best, costs[p] + solve(j));
}
return best;
};
return solve(0);
}2Optimal (DP over calendar days)
O(D)D is the last travel day (at most 365); each day is processed in O(1).O(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.
- last = days[n - 1]; mark the travel days in a boolean array.
- dp[0] = 0. For d from 1 to last: if d is not a travel day, dp[d] = dp[d - 1].
- Otherwise 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].
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];
}
}class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
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]
continue
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]class Solution {
public:
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];
continue;
}
int one = dp[d - 1] + costs[0];
int week = dp[max(0, d - 7)] + costs[1];
int month = dp[max(0, d - 30)] + costs[2];
dp[d] = min(one, min(week, month));
}
return dp[last];
}
};function mincostTickets(days, costs) {
const last = days[days.length - 1];
const travel = new Array(last + 1).fill(false);
for (const d of days) travel[d] = true;
const dp = new Array(last + 1).fill(0);
for (let d = 1; d <= last; d++) {
if (!travel[d]) {
dp[d] = dp[d - 1];
continue;
}
const one = dp[d - 1] + costs[0];
const week = dp[Math.max(0, d - 7)] + costs[1];
const month = dp[Math.max(0, d - 30)] + costs[2];
dp[d] = Math.min(one, 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.