Problem

You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.

Train tickets are sold in three different ways:

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

The passes allow that many days of consecutive travel.

  • For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Examples

Example 1

1
2
3
4
5
6
7

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

Example 2

1
2
3
4
5
6

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.

Solution

Method 1 - Recursion

Intuition

The problem asks for the minimum cost to cover all travel days using tickets of different durations. The naive recursive approach tries every possible way to buy tickets for each travel day, considering all ticket types at each step.

Approach

At each travel day, we can:

  • Buy a 1-day pass and move to the next day.
  • Buy a 7-day pass and skip all days covered by it.
  • Buy a 30-day pass and skip all days covered by it.

We recursively try all options and take the minimum cost.

Recurrence Relation

Let f(i) be the minimum cost to cover travel days starting from index i:

  • f(i) = min(cost_1 + f(next_1), cost_7 + f(next_7), cost_30 + f(next_30)) Where next_x is the next index not covered by the x-day pass bought at days[i].
Base Case

If i >= len(days), return 0 (no more days to cover).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        return dfs(days, costs, 0);
    }
    int dfs(vector<int>& days, vector<int>& costs, int i) {
        if (i >= days.size()) return 0;
        int cost1 = costs[0] + dfs(days, costs, i + 1);
        int j = i;
        while (j < days.size() && days[j] < days[i] + 7) ++j;
        int cost7 = costs[1] + dfs(days, costs, j);
        j = i;
        while (j < days.size() && days[j] < days[i] + 30) ++j;
        int cost30 = costs[2] + dfs(days, costs, j);
        return min({cost1, cost7, cost30});
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func mincostTickets(days []int, costs []int) int {
    var dfs func(i int) int
    dfs = func(i int) int {
        if i >= len(days) {
            return 0
        }
        cost1 := costs[0] + dfs(i+1)
        j := i
        for j < len(days) && days[j] < days[i]+7 {
            j++
        }
        cost7 := costs[1] + dfs(j)
        j = i
        for j < len(days) && days[j] < days[i]+30 {
            j++
        }
        cost30 := costs[2] + dfs(j)
        return min(cost1, min(cost7, cost30))
    }
    return dfs(0)
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        return dfs(days, costs, 0);
    }
    private int dfs(int[] days, int[] costs, int i) {
        if (i >= days.length) return 0;
        int cost1 = costs[0] + dfs(days, costs, i + 1);
        int j = i;
        while (j < days.length && days[j] < days[i] + 7) j++;
        int cost7 = costs[1] + dfs(days, costs, j);
        j = i;
        while (j < days.length && days[j] < days[i] + 30) j++;
        int cost30 = costs[2] + dfs(days, costs, j);
        return Math.min(cost1, Math.min(cost7, cost30));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun mincostTickets(days: IntArray, costs: IntArray): Int {
        fun dfs(i: Int): Int {
            if (i >= days.size) return 0
            val cost1 = costs[0] + dfs(i + 1)
            var j = i
            while (j < days.size && days[j] < days[i] + 7) j++
            val cost7 = costs[1] + dfs(j)
            j = i
            while (j < days.size && days[j] < days[i] + 30) j++
            val cost30 = costs[2] + dfs(j)
            return minOf(cost1, cost7, cost30)
        }
        return dfs(0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        def dfs(i):
            if i >= len(days):
                return 0
            cost1 = costs[0] + dfs(i + 1)
            j = i
            while j < len(days) and days[j] < days[i] + 7:
                j += 1
            cost7 = costs[1] + dfs(j)
            j = i
            while j < len(days) and days[j] < days[i] + 30:
                j += 1
            cost30 = costs[2] + dfs(j)
            return min(cost1, cost7, cost30)
        return dfs(0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn mincost_tickets(days: Vec<i32>, costs: Vec<i32>) -> i32 {
        fn dfs(days: &Vec<i32>, costs: &Vec<i32>, i: usize) -> i32 {
            if i >= days.len() {
                return 0;
            }
            let cost1 = costs[0] + dfs(days, costs, i + 1);
            let mut j = i;
            while j < days.len() && days[j] < days[i] + 7 {
                j += 1;
            }
            let cost7 = costs[1] + dfs(days, costs, j);
            j = i;
            while j < days.len() && days[j] < days[i] + 30 {
                j += 1;
            }
            let cost30 = costs[2] + dfs(days, costs, j);
            *[cost1, cost7, cost30].iter().min().unwrap()
        }
        dfs(&days, &costs, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    mincostTickets(days: number[], costs: number[]): number {
        function dfs(i: number): number {
            if (i >= days.length) return 0;
            const cost1 = costs[0] + dfs(i + 1);
            let j = i;
            while (j < days.length && days[j] < days[i] + 7) j++;
            const cost7 = costs[1] + dfs(j);
            j = i;
            while (j < days.length && days[j] < days[i] + 30) j++;
            const cost30 = costs[2] + dfs(j);
            return Math.min(cost1, cost7, cost30);
        }
        return dfs(0);
    }
}

Complexity

  • ⏰ Time complexity: O(3^n), where n is the number of travel days, since each day can branch into three choices.
  • 🧺 Space complexity: O(n), due to recursion stack.

Method 2 - Recursion with Memoization

Intuition

To avoid redundant calculations, we store the minimum cost for each starting index in a memoization table. This ensures each subproblem is solved only once, making the solution much faster than plain recursion.

Approach

  1. For each travel day, consider three choices:
    • Buy a 1-day pass and move to the next day.
    • Buy a 7-day pass and skip all days covered by it.
    • Buy a 30-day pass and skip all days covered by it.
  2. Use a memoization table to store the minimum cost for each starting index.
  3. For each ticket type, find the next index not covered by the ticket.
  4. Recursively compute the minimum cost for each option and store the result.
  5. The base case is when all days are covered (index out of bounds), return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> memo(days.size(), -1);
        return dfs(days, costs, 0, memo);
    }
    int dfs(vector<int>& days, vector<int>& costs, int i, vector<int>& memo) {
        if (i >= days.size()) return 0;
        if (memo[i] != -1) return memo[i];
        int cost1 = costs[0] + dfs(days, costs, i + 1, memo);
        int j = i;
        while (j < days.size() && days[j] < days[i] + 7) j++;
        int cost7 = costs[1] + dfs(days, costs, j, memo);
        j = i;
        while (j < days.size() && days[j] < days[i] + 30) j++;
        int cost30 = costs[2] + dfs(days, costs, j, memo);
        return memo[i] = min({cost1, cost7, cost30});
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func mincostTickets(days []int, costs []int) int {
    memo := make(map[int]int)
    var dfs func(i int) int
    dfs = func(i int) int {
        if i >= len(days) {
            return 0
        }
        if v, ok := memo[i]; ok {
            return v
        }
        cost1 := costs[0] + dfs(i+1)
        j := i
        for j < len(days) && days[j] < days[i]+7 {
            j++
        }
        cost7 := costs[1] + dfs(j)
        j = i
        for j < len(days) && days[j] < days[i]+30 {
            j++
        }
        cost30 := costs[2] + dfs(j)
        ans := min(cost1, min(cost7, cost30))
        memo[i] = ans
        return ans
    }
    return dfs(0)
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int[] memo = new int[days.length];
        Arrays.fill(memo, -1);
        return dfs(days, costs, 0, memo);
    }
    private int dfs(int[] days, int[] costs, int i, int[] memo) {
        if (i >= days.length) return 0;
        if (memo[i] != -1) return memo[i];
        int cost1 = costs[0] + dfs(days, costs, i + 1, memo);
        int j = i;
        while (j < days.length && days[j] < days[i] + 7) j++;
        int cost7 = costs[1] + dfs(days, costs, j, memo);
        j = i;
        while (j < days.length && days[j] < days[i] + 30) j++;
        int cost30 = costs[2] + dfs(days, costs, j, memo);
        memo[i] = Math.min(cost1, Math.min(cost7, cost30));
        return memo[i];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun mincostTickets(days: IntArray, costs: IntArray): Int {
        val memo = IntArray(days.size) { -1 }
        fun dfs(i: Int): Int {
            if (i >= days.size) return 0
            if (memo[i] != -1) return memo[i]
            val cost1 = costs[0] + dfs(i + 1)
            var j = i
            while (j < days.size && days[j] < days[i] + 7) j++
            val cost7 = costs[1] + dfs(j)
            j = i
            while (j < days.size && days[j] < days[i] + 30) j++
            val cost30 = costs[2] + dfs(j)
            memo[i] = minOf(cost1, cost7, cost30)
            return memo[i]
        }
        return dfs(0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from typing import List

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        memo: dict[int, int] = {}
        def dfs(i: int) -> int:
            if i >= len(days):
                return 0
            if i in memo:
                return memo[i]
            cost1 = costs[0] + dfs(i + 1)
            j = i
            while j < len(days) and days[j] < days[i] + 7:
                j += 1
            cost7 = costs[1] + dfs(j)
            j = i
            while j < len(days) and days[j] < days[i] + 30:
                j += 1
            cost30 = costs[2] + dfs(j)
            memo[i] = min(cost1, cost7, cost30)
            return memo[i]
        return dfs(0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn mincost_tickets(days: Vec<i32>, costs: Vec<i32>) -> i32 {
        fn dfs(days: &Vec<i32>, costs: &Vec<i32>, i: usize, memo: &mut Vec<i32>) -> i32 {
            if i >= days.len() {
                return 0;
            }
            if memo[i] != -1 {
                return memo[i];
            }
            let cost1 = costs[0] + dfs(days, costs, i + 1, memo);
            let mut j = i;
            while j < days.len() && days[j] < days[i] + 7 {
                j += 1;
            }
            let cost7 = costs[1] + dfs(days, costs, j, memo);
            j = i;
            while j < days.len() && days[j] < days[i] + 30 {
                j += 1;
            }
            let cost30 = costs[2] + dfs(days, costs, j, memo);
            let ans = *[cost1, cost7, cost30].iter().min().unwrap();
            memo[i] = ans;
            ans
        }
        let mut memo = vec![-1; days.len()];
        dfs(&days, &costs, 0, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    mincostTickets(days: number[], costs: number[]): number {
        const memo: Record<number, number> = {};
        function dfs(i: number): number {
            if (i >= days.length) return 0;
            if (memo[i] !== undefined) return memo[i];
            const cost1 = costs[0] + dfs(i + 1);
            let j = i;
            while (j < days.length && days[j] < days[i] + 7) j++;
            const cost7 = costs[1] + dfs(j);
            j = i;
            while (j < days.length && days[j] < days[i] + 30) j++;
            const cost30 = costs[2] + dfs(j);
            memo[i] = Math.min(cost1, cost7, cost30);
            return memo[i];
        }
        return dfs(0);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of travel days. Each subproblem (index) is solved only once due to memoization.
  • 🧺 Space complexity: O(n), for the memoization table and recursion stack.

Method 3 - Tabulation (Bottom-Up DP)

Intuition

Instead of solving the problem recursively, we build the solution from the end to the start using a DP table. For each travel day, we compute the minimum cost to cover all remaining days, using previously computed results for future days.

Approach

  1. Create a DP array of size n+1 (where n is the number of travel days), with dp[n] = 0 (no cost after last day).
  2. Iterate backwards from the last travel day to the first.
  3. For each index, consider three options:
    • Buy a 1-day pass and add its cost to dp[i+1].
    • Buy a 7-day pass and add its cost to dp[next_7], where next_7 is the first index not covered by the 7-day pass.
    • Buy a 30-day pass and add its cost to dp[next_30], where next_30 is the first index not covered by the 30-day pass.
  4. Set dp[i] to the minimum of these three options.
  5. Return dp[0] as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> dp(n + 1, 0);
        for (int i = n - 1; i >= 0; --i) {
            int cost1 = costs[0] + dp[i + 1];
            int j = i;
            while (j < n && days[j] < days[i] + 7) j++;
            int cost7 = costs[1] + dp[j];
            j = i;
            while (j < n && days[j] < days[i] + 30) j++;
            int cost30 = costs[2] + dp[j];
            dp[i] = min({cost1, cost7, cost30});
        }
        return dp[0];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func mincostTickets(days []int, costs []int) int {
    n := len(days)
    dp := make([]int, n+1)
    for i := n - 1; i >= 0; i-- {
        cost1 := costs[0] + dp[i+1]
        j := i
        for j < n && days[j] < days[i]+7 {
            j++
        }
        cost7 := costs[1] + dp[j]
        j = i
        for j < n && days[j] < days[i]+30 {
            j++
        }
        cost30 := costs[2] + dp[j]
        dp[i] = min(cost1, min(cost7, cost30))
    }
    return dp[0]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int cost1 = costs[0] + dp[i + 1];
            int j = i;
            while (j < n && days[j] < days[i] + 7) j++;
            int cost7 = costs[1] + dp[j];
            j = i;
            while (j < n && days[j] < days[i] + 30) j++;
            int cost30 = costs[2] + dp[j];
            dp[i] = Math.min(cost1, Math.min(cost7, cost30));
        }
        return dp[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun mincostTickets(days: IntArray, costs: IntArray): Int {
        val n = days.size
        val dp = IntArray(n + 1)
        for (i in n - 1 downTo 0) {
            val cost1 = costs[0] + dp[i + 1]
            var j = i
            while (j < n && days[j] < days[i] + 7) j++
            val cost7 = costs[1] + dp[j]
            j = i
            while (j < n && days[j] < days[i] + 30) j++
            val cost30 = costs[2] + dp[j]
            dp[i] = minOf(cost1, cost7, cost30)
        }
        return dp[0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from typing import List

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            cost1 = costs[0] + dp[i + 1]
            j = i
            while j < n and days[j] < days[i] + 7:
                j += 1
            cost7 = costs[1] + dp[j]
            j = i
            while j < n and days[j] < days[i] + 30:
                j += 1
            cost30 = costs[2] + dp[j]
            dp[i] = min(cost1, cost7, cost30)
        return dp[0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn mincost_tickets(days: Vec<i32>, costs: Vec<i32>) -> i32 {
        let n = days.len();
        let mut dp = vec![0; n + 1];
        for i in (0..n).rev() {
            let cost1 = costs[0] + dp[i + 1];
            let mut j = i;
            while j < n && days[j] < days[i] + 7 {
                j += 1;
            }
            let cost7 = costs[1] + dp[j];
            j = i;
            while j < n && days[j] < days[i] + 30 {
                j += 1;
            }
            let cost30 = costs[2] + dp[j];
            dp[i] = *[cost1, cost7, cost30].iter().min().unwrap();
        }
        dp[0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    mincostTickets(days: number[], costs: number[]): number {
        const n = days.length;
        const dp = new Array(n + 1).fill(0);
        for (let i = n - 1; i >= 0; i--) {
            const cost1 = costs[0] + dp[i + 1];
            let j = i;
            while (j < n && days[j] < days[i] + 7) j++;
            const cost7 = costs[1] + dp[j];
            j = i;
            while (j < n && days[j] < days[i] + 30) j++;
            const cost30 = costs[2] + dp[j];
            dp[i] = Math.min(cost1, cost7, cost30);
        }
        return dp[0];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the number of travel days. For each day, we may scan up to n days to find the next index not covered by a pass.
  • 🧺 Space complexity: O(n), for the DP table.