983. Minimum Cost For Tickets

983. Minimum Cost For Tickets

 

https://youtu.be/4pY1bsBpIY4?si=PbuLW3CZC5vqdJDg

 

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = {}

        def dfs(i):
            if i == len(days):
                return 0
            if i in dp:
                return dp[i]

            dp[i] = float("inf")
            # d: # of days, c: cost
            for d, c in zip([1, 7, 30], costs):
                j = i
                while j < len(days) and days[j] < days[i] + d:
                    j += 1
                dp[i] = min(dp[i], c + dfs(j))
            return dp[i]

        return dfs(0) # 여기서 i=0 는 days array 의 index 임