from functools import lru_cache
class Solution:
# time O(W) W: max travelrable days, 365.
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
duration = [1,7,30]
@lru_cache(None)
def dp(i):
if i > 365:
return 0
elif i in days:
return min(dp(i+d) + c for c,d in zip(costs, duration))
else:
return dp(i+1)
return dp(1)
from functools import lru_cache
class Solution:
# time O(end - start) space O(end)
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
duration = [1,7,30]
start,end = days[0], days[-1]
length = len(days)
dp = [0] * (end + 31)
d = end
i = length -1
while d >= start:
if d == days[i]:
dp[d] = min(dp[d+1]+costs[0],dp[d+7]+costs[1],dp[d+30]+costs[2])
i -= 1
else:
dp[d] = dp[d+1]
d -= 1
return dp[start]