DSA problem
Minimum Cost For Tickets
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 that costs costs[0], a 7-day pass that costs costs[1], and a 30-day pass that costs costs[2]. The passes allow consecutive travel: for example, if you get a 7-day pass on day 2, you can travel for 7 consecutive days (days 2 through 8). Return the minimum number of dollars you need to travel every day in the given list of days.
This is an unbounded-knapsack variant: at every travel day you decide which of three pass types to "buy" (each can be used unlimited times across the year), and the goal is to minimize the total cost. Although passes give you 1, 7, or 30 consecutive days of coverage, a clean reformulation lets us iterate over each calendar day and decide the cheapest way to cover up to and including that day.
Let dp[d] be the minimum cost to cover all travel days up to and including calendar day d, for d from 0 to the last travel day. The base case is dp[0] = 0. If day d is NOT in the travel set, we owe nothing extra for day d, so dp[d] = dp[d - 1]. If day d IS a travel day, we must have just bought one of the three passes that covers day d, giving dp[d] = min(dp[d - 1] + costs[0], dp[max(0, d - 7)] + costs[1], dp[max(0, d - 30)] + costs[2]).
To check membership efficiently, convert days into a hash set first so each lookup is O(1). The total runtime is O(D) where D is the last travel day, and the extra space is O(D) for the DP table plus O(len(days)) for the set. The answer is dp[last_day].
Examples
days = [1,4,6,7,8,20], costs = [2,7,15]11days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]17days = [1], costs = [2,7,15]2Constraints
- 1 <= days.length <= 365
- 1 <= days[i] <= 365
- days is in strictly increasing order.
- costs.length == 3
- 1 <= costs[i] <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.