#983

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Cost For Tickets

Solve the Minimum Cost For Tickets problem using state transition dynamic programming for optimal travel ticket purchases efficiently.

array dynamic programming

Problem Statement

You are planning train travel for the entire year, and the days you intend to travel are given in an array days, each an integer from 1 to 365. Train tickets are sold as 1-day, 7-day, or 30-day passes, each costing amounts specified in an array costs. Each pass covers consecutive travel days for its duration, and you can buy any number of passes.

Determine the minimum total cost to cover all travel days in days. You must decide which combination of ticket types to buy so that every travel day is covered while minimizing the sum of costs. Your solution should handle up to 365 days efficiently using state transition dynamic programming.

Examples

Example 1

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

Output: 11

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

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]

Output: 17

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.

Constraints

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

Solution Approach

Dynamic Programming State Definition

Define dp[i] as the minimum cost to cover travel up to day i. Initialize dp[0] = 0. Iterate through all days, updating dp[day] by considering buying a 1-day, 7-day, or 30-day pass, using dp[previous_day] + cost for each option.

Efficient Lookup of Previous States

Use a set or array to quickly check if a given day is a travel day. For days not in days[], dp[day] = dp[day-1] to carry forward the minimum cost without extra purchase, ensuring only travel days trigger cost addition.

Iterative Transition and Minimization

For each travel day, compute the cost for all three pass types and choose the minimum. dp[day] = min(dp[day-1]+cost1, dp[max(0, day-7)]+cost7, dp[max(0, day-30)]+cost30). Iterate sequentially to build up the dp array efficiently.

Complexity Analysis

Metric	Value
Time	O(K)
Space	O(K)

Time complexity is O(K) where K is the last travel day since each day requires constant-time computations for the three pass options. Space complexity is O(K) for storing dp values for each day. This avoids redundant recalculations and scales linearly with the range of travel days.

What Interviewers Usually Probe

Are you considering all ticket durations for each travel day?
Can you optimize without checking every day from 1 to 365?
Do you correctly handle days not in the travel plan to skip unnecessary costs?

Common Pitfalls or Variants

Common pitfalls

Failing to skip non-travel days, causing extra cost calculations.
Incorrectly indexing dp for 7-day or 30-day passes, leading to out-of-bounds errors.
Choosing a greedy approach instead of evaluating all pass options per travel day, which fails for overlapping passes.

Follow-up variants

Consider variations with different pass durations and costs, affecting state transitions.
Limit travel days to random sparse subsets, testing DP efficiency and correctness.
Use different cost structures, like discounted multi-pass bundles, changing the transition rules.

FAQ

What is the key pattern to solve Minimum Cost For Tickets?

State transition dynamic programming is the core pattern, using dp[i] to track minimum cost up to each travel day.

How do I handle non-travel days efficiently?

For days not in the travel schedule, simply carry forward dp[day] = dp[day-1] to avoid unnecessary cost computation.

Can a greedy approach work for this problem?

No, greedy selection fails because longer passes may overlap future travel days, making DP essential to find the minimum total cost.

What is the time complexity of this solution?

Time complexity is O(K), where K is the maximum travel day, since each day considers only three ticket options.

How do I handle the 7-day and 30-day passes in the DP array?

Use dp[max(0, day-7)] and dp[max(0, day-30)] to safely access previous states while calculating the minimum cost for longer passes.

terminal

Solution

Solution 1: Memoization Search + Binary Search

We define a function $\textit{dfs(i)}$, which represents the minimum cost required from the $i$-th trip to the last trip. Thus, the answer is $\textit{dfs(0)}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            ans = inf
            for c, v in zip(costs, valid):
                j = bisect_left(days, days[i] + v)
                ans = min(ans, c + dfs(j))
            return ans

        n = len(days)
        valid = [1, 7, 30]
        return dfs(0)

Solution 2: Dynamic Programming

Let's denote the last day in the $\textit{days}$ array as $m$. We can define an array $f$ of length $m + 1$, where $f[i]$ represents the minimum cost from day $1$ to day $i$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            ans = inf
            for c, v in zip(costs, valid):
                j = bisect_left(days, days[i] + v)
                ans = min(ans, c + dfs(j))
            return ans

        n = len(days)
        valid = [1, 7, 30]
        return dfs(0)

Continue Practicing

#978 longest turbulent subarray #975 odd even jump #996 number of squareful arrays