Minimum Cost For Tickets

983. Minimum Cost For Tickets

Average Rating: 4.14 (35 votes)

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.

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
- Approach 1: Dynamic Programming (Day Variant)
- Approach 2: Dynamic Programming (Window Variant)

Solution

Approach 1: Dynamic Programming (Day Variant)

Intuition and Algorithm

For each day, if you don't have to travel today, then it's strictly better to wait to buy a pass. If you have to travel today, you have up to 3 choices: you must buy either a 1-day, 7-day, or 30-day pass.

We can express those choices as a recursion and use dynamic programming. Let's say dp(i) is the cost to fulfill your travel plan from day i to the end of the plan. Then, if you have to travel today, your cost is:

$\text{dp}(i) = \min(\text{dp}(i+1) + \text{costs}[0], \text{dp}(i+7) + \text{costs}[1], \text{dp}(i+30) + \text{costs}[2])$

Complexity Analysis

Time Complexity: $O(W)$ , where $W = 365$ is the maximum numbered day in your travel plan.
Space Complexity: $O(W)$ .

Approach 2: Dynamic Programming (Window Variant)

Intuition and Algorithm

As in Approach 1, we only need to buy a travel pass on a day we intend to travel.

Now, let dp(i) be the cost to travel from day days[i] to the end of the plan. If say, j1 is the largest index such that days[j1] < days[i] + 1, j7 is the largest index such that days[j7] < days[i] + 7, and j30 is the largest index such that days[j30] < days[i] + 30, then we have:

$\text{dp}(i) = \min(\text{dp}(j1) + \text{costs}[0], \text{dp}(j7) + \text{costs}[1], \text{dp}(j30) + \text{costs}[2])$

Complexity Analysis

Time Complexity: $O(N)$ , where $N$ is the number of unique days in your travel plan.
Space Complexity: $O(N)$ .

Analysis written by: @awice.