https://leetcode.com/problems/minimum-cost-for-tickets
최소 티켓 비용 – LeetCode
이 실제 인터뷰 질문을 해결할 수 있습니까? 티켓의 최소 비용 – 1년 전에 기차 여행을 계획했습니다. 여행할 날짜는 날짜의 정수 배열로 지정됩니다. 매일은 1부터 365까지의 정수입니다. 기차
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)