23.03.28 Today’s leetcode

983. Minimum Cost For Tickets (medium)

DFS Approach : TLE

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        def dfs(cur, cost):
            if days[-1] <= cur:
                return cost
            for day in days:
                if day > cur:
                    cur = day
                    break
            temp = math.inf
            temp = min(temp, dfs(cur + 1, cost + costs[0]))
            temp = min(temp, dfs(cur + 7, cost + costs[1]))
            temp = min(temp, dfs(cur + 30, cost + costs[2]))
            return temp

        return dfs(0, 0)

DP Approach

class Solution:
    def mincostTickets(self, days, costs):
    
        dp = [0] * 366
        travel_days = set(days)
        for i in range(1, 366):
            if i not in travel_days:
                dp[i] = dp[i-1]
            else:
                dp[i] = min(dp[i-1] + costs[0], dp[max(0, i-7)] + costs[1], dp[max(0, i-30)] + costs[2])
        return dp[365]