Dynamic Programming

983. Minimum Cost For Tickets

You are given a list of days which you are traveling on. To travel you are required to buy a ticket for each day, there are three types of ticket passes with different costs that you can buy, each pass covers your travel for a consecutive number of days:

1-day pass(costs[0])
7-day pass(costs[1])
30-day pass(costs[2])

The goal is the find the minimum cost to be able to travel on all the given days.

Example:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
You buy a 1-day pass for day 1, a 7-day pass(covering day 4 through day 10) for days 4,6,7,8 and a 1-day pass for day 20.

Solution:

Approach: DP with memoization. Define an array dp where dp[i] represents the minimum cost to travel each day in the given list of days AND not later than day i. For example, in the above example, dp[4] and dp[5] are both the minimum cost required to travel on days=[1,4]. The final answer is equal to dp[365] or dp[max(days)].

1
class Solution:
2
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
3
        # The minimum cost required to travel each day
4
        # in the given list of days AND not later than day i.
5
        # The final answer is equal to dp[365] or dp[max(days)]
6
        dp = [0] * 366
7
        for i in range(1, 366):
8
            dp[i] = dp[i-1]
9
            if i in days:
10
                dp[i] = min(dp[i-1]+costs[0], dp[max(0,i-7)]+costs[1], dp[max(0, i-30)]+costs[2])
11
        return dp[365]