Question 983. Minimum Cost For Tickets

Link

https://leetcode.com/problems/minimum-cost-for-tickets/

My code

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        if len(days) ==0:
            return 0
        else:
            CostList = [0] #Initialise for the day 0, the cost is always 0
            TotalNumberDays = days[-1]
            for i in range(1,TotalNumberDays+1):
                if i not in days:
                    CostList.append(CostList[i-1])
                else:
                    Index1 = max(i-1,0)
                    Index2 = max(i-7,0)
                    Index3 = max(i-30,0)
                    value1 = CostList[Index1]+costs[0]
                    value2 = CostList[Index2]+ costs[1]
                    value3 = CostList[Index3]+ costs[2]
                    Min1  = min(value1,value2)
                    Min2 = min(Min1,value3)
                    CostList.append(Min2)
        return CostList[TotalNumberDays]

Explanation:

The idea is this: On a specific day, we want to know if it is included in the specific ticket. There are two situations: if that day is not included in the travel days, then we just keep the value as it is yesterday ( i-1). The other situation is that it is in the travel days, then we want to know which ticket length does it take. To maximize the usage, we definitely want to make that day as the last day of the ticket. if that day is not the last day of the ticket, we can simply achieve a not worse result by purchasing the ticket one day before as the total cost of the ticket is non decreasing as the day increases. Hence we have three values, given by three length of the ticket. Then we take the minimum of these three as the minimum  value of the day on the year so far.