Intuition
Complexity
Runtime
Space
Code
Bottom Up
Top Down
Slight Optimization
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
@cache
def r(day, cost, unpaid_day_index):
unpaid_day = -1
for i in reversed(range(unpaid_day_index)):
if day >= days[i]:
unpaid_day = days[i]
unpaid_day_index = i
break
if unpaid_day < 0:
return cost
o1 = cost + r(unpaid_day - 1, costs[0], unpaid_day_index)
o2 = cost + r(unpaid_day - 7, costs[1], unpaid_day_index)
o3 = cost + r(unpaid_day - 30, costs[2], unpaid_day_index)
return min(o1, o2, o3)
return r(days[-1], 0, len(days))
Uncapped For Loop
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
@cache
def r(day, cost):
unpaid_day = -1
for i in reversed(range(len(days))):
if day >= days[i]:
unpaid_day = days[i]
break
if unpaid_day < 0:
return cost
o1 = cost + r(unpaid_day - 1, costs[0])
o2 = cost + r(unpaid_day - 7, costs[1])
o3 = cost + r(unpaid_day - 30, costs[2])
return min(o1, o2, o3)
return r(days[-1], 0)
Notes
Cards
References