LC 0983 [M] Minimum Cost For Tickets - ALawliet/algorithms GitHub Wiki

similar to House Robber

https://leetcode.com/problems/minimum-cost-for-tickets/discuss/810749/Python-by-DP-w-Visualization https://leetcode.com/problems/minimum-cost-for-tickets/discuss/228421/Python-solution https://leetcode.com/problems/minimum-cost-for-tickets/discuss/227321/Top-down-DP-Logical-Thinking

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = {} # index to min cost
        
        def dfs(i):
            if i == len(days):
                return 0
            if i in dp:
                return dp[i]
            
            dp[i] = float('inf')
            for d, c in zip([1,7,30], costs):
                next_i = i # jump to the next day we need to travel and only store that, skip the ones we already passed
                while next_i < len(days) and days[next_i] < days[i] + d:
                    next_i += 1 
                dp[i] = min(dp[i], dfs(next_i) + c)
                
            return dp[i]
        
        return dfs(0)

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        # Create dictionary for faster lookup of days
        days_dict = Counter(days)
        
        # Create a table of all the day cost
        # * Instead of creating a 365 days table, we create until the last day on the days list
        T = [0 for i in range(0, days[-1]+1)]
        
        for i in range(0, days[-1]+1):
            # If the current day is not present in the travel days dictionary, it takes the previous value
            if i not in days_dict:
                T[i] = T[i-1]
            else:
                # Used max to identify if the index exists 
                T[i] = min(
                    T[max(0,i-1)] + costs[0], # per days value
                    T[max(0,i-7)] + costs[1], # per week value
                    T[max(0,i-30)] + costs[2] # per year value
                )
       
        return T[-1]

private int[] memo;
    
    public int mincostTickets(int[] days, int[] costs) {
        memo = new int[days.length];
        return mincostTickets(0, days, costs);
    }
    
    private int mincostTickets(int dayIndex, int[] days, int[] costs) {
        if (dayIndex == days.length) {
            return 0;
        }
        
        if (memo[dayIndex] != 0) {
            return memo[dayIndex];
        }
        
        // Choose a pass, update dayIndex, and accumulate totalCost
        int totalCostDay = costs[0] + mincostTickets(getNextDayToBuy(dayIndex, days, 1), days, costs);   
        int totalCostWeek = costs[1] + mincostTickets(getNextDayToBuy(dayIndex, days, 7), days, costs);
        int totalCostMonth = costs[2] + mincostTickets(getNextDayToBuy(dayIndex, days, 30), days, costs);
        
        // Return the one with min totalCost
        memo[dayIndex] = Math.min(totalCostMonth, Math.min(totalCostDay, totalCostWeek));
        return memo[dayIndex];
    }
    
    private int getNextDayToBuy(int dayIndex, int[] days, int duration) {
        int endDay = days[dayIndex] + duration - 1;
        int newDayIndex = dayIndex;
		
        while (newDayIndex < days.length && days[newDayIndex] <= endDay) {
            newDayIndex++;
        }
        
        return newDayIndex;
    }