LC 983. Minimum Cost For Tickets

lc983.py

class Solution:    
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        # S[i] = min total cost to travel for up to i days
        # S[i] =
        #   min(S[i-1] + costs[0], S[i-7] + costs[1], S[i-30] + costs[2])   if i is in days
        #   S[i-1]                                                          otherwise
        # answer is S[-1]
        
        # so either it is cheaper to check the price 7 days ago with the cost of a 7 day
        # pass, or our pass is still in service, so the price does not change
        # same for the 30 day pass
        
        # Make the array as big as the number of days, plus 1 (because we start at 0)
        S = [0] * (days[-1] + 1)
        for i in range(1, len(S)):
            # If today is a day we are going on a trip...
            if i in days:
                # Make sure a pass this long is even possible
                # Get the minimum cost for a trip this long
                if (i - 30) > 0:
                    S[i] = min(S[i - 1] + costs[0], S[i - 7] + costs[1], S[i - 30] + costs[2])
                elif (i - 7) > 0:
                    S[i] = min(S[i - 1] + costs[0], S[i - 7] + costs[1], costs[2])
                else:
                    S[i] = min(S[i - 1] + costs[0], costs[1], costs[2])
            # It's a regular day, we didn't spend anything
            else:
                S[i] = S[i-1]
                
            print(S)
        # Return the final cost
        return S[-1]