파비의 매일매일 공부기록

2023.03.28 Today's Challenge 본문

Problem Solving/LeetCode

2023.03.28 Today's Challenge

fabichoi 2023. 3. 28. 23:45

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

 

Minimum Cost For Tickets - LeetCode

Can you solve this real interview question? Minimum Cost For Tickets - You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365. Train

leetcode.com

DP 로 푸는 문제. DFS/BFS에서 DP 나오는걸로 바뀐 듯 ㅋㅋ

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dayset = set(days)
        durations = [1, 7, 30]

        @lru_cache(None)
        def dp(i):
            if i > 365:
                return 0
            elif i in dayset:
                return min(dp(i+d) + c for c, d in zip(costs, durations))
            else:
                return dp(i+1)
        
        return dp(1)

 

 

반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.03.30 Today's Challenge  (0) 2023.03.30
2023.03.29 Today's Challenge  (0) 2023.03.29
2023.03.27 Today's Challenge  (0) 2023.03.27
2023.03.26 Today's Challenge  (0) 2023.03.26
2023.03.25 Today's Challenge  (0) 2023.03.25
'Problem Solving/LeetCode' Related Articles more
Comments