Leetcode 983. Minimum Cost For Tickets (Python)

Related Topic

Dynamic-Programming.

Description

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

• 1-day pass is sold for costs[0] dollars;
• 7-day pass is sold for costs[1] dollars;
• 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: day 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.

Sample I/O

Example 1

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

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.

Methodology

This question solved by Dynamic Programming. It is similar with question 322. Coin Change.

This question can be solved by Dynamic Programming. Create dp list to indicate the minimum cost for each day. The dp list size should be the last day + 1. Init the first element of dp list to 0 because there is 0 cost for 0 day. Then we iterate the days list, if the current day not in days list, we let the current day’s cost equal the previous day’cost. Otherwise ,we need to compare among the current day minus one day, minus 7 days and minus 30 days’ cost and find the minimum cost for the current day.

Base case:

We create dp list and init each value to max_cost of all time(here should be max(costs)*size). Init 0 index as 0 because the number of cost for day 0 is 0.

We are also given a ticket list implicitly here is [1,7,30]

Pattern

Iterate the day of days list if the day is not in the days, the minimum cost of the day is equal to previous day. Otherwise if the day is in days. Then find the minimum cost among current day - 1 + cost[0], current day - 7+[1], current day - 30+cost[2]. Update the current day with the minimum cost

Result

The last value of dp indicate the total minimum cost for the whole travel plan.

Code

def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        size =days[-1]
        max_cost = max(costs)*size
        dp=[0]+[max_cost]*size
        ticket_price={1:costs[0],7:costs[1],30:costs[2]}
        
        for day in range(1,len(dp)):
            if day not in days:
                dp[day]=dp[day-1]
                continue
            for ticket in [1,7,30]:
                if day>=ticket:
                    dp[day]=min(dp[day],dp[day-ticket]+ticket_price[ticket])
                else:
                    dp[day]=min(dp[day],dp[0]+ticket_price[ticket])
        return dp[-1]

BigO

We iterate all dp array, it will cost O(n), inside the iteration, we need to iterate the tickets which is O(3) So the total time complexity is O(3n) which is O(n)