LC 0983 [M] Minimum Cost For Tickets - ALawliet/algorithms GitHub Wiki
similar to House Robber
https://leetcode.com/problems/minimum-cost-for-tickets/discuss/810749/Python-by-DP-w-Visualization https://leetcode.com/problems/minimum-cost-for-tickets/discuss/228421/Python-solution https://leetcode.com/problems/minimum-cost-for-tickets/discuss/227321/Top-down-DP-Logical-Thinking
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
dp = {} # index to min cost
def dfs(i):
if i == len(days):
return 0
if i in dp:
return dp[i]
dp[i] = float('inf')
for d, c in zip([1,7,30], costs):
next_i = i # jump to the next day we need to travel and only store that, skip the ones we already passed
while next_i < len(days) and days[next_i] < days[i] + d:
next_i += 1
dp[i] = min(dp[i], dfs(next_i) + c)
return dp[i]
return dfs(0)
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
# Create dictionary for faster lookup of days
days_dict = Counter(days)
# Create a table of all the day cost
# * Instead of creating a 365 days table, we create until the last day on the days list
T = [0 for i in range(0, days[-1]+1)]
for i in range(0, days[-1]+1):
# If the current day is not present in the travel days dictionary, it takes the previous value
if i not in days_dict:
T[i] = T[i-1]
else:
# Used max to identify if the index exists
T[i] = min(
T[max(0,i-1)] + costs[0], # per days value
T[max(0,i-7)] + costs[1], # per week value
T[max(0,i-30)] + costs[2] # per year value
)
return T[-1]
private int[] memo;
public int mincostTickets(int[] days, int[] costs) {
memo = new int[days.length];
return mincostTickets(0, days, costs);
}
private int mincostTickets(int dayIndex, int[] days, int[] costs) {
if (dayIndex == days.length) {
return 0;
}
if (memo[dayIndex] != 0) {
return memo[dayIndex];
}
// Choose a pass, update dayIndex, and accumulate totalCost
int totalCostDay = costs[0] + mincostTickets(getNextDayToBuy(dayIndex, days, 1), days, costs);
int totalCostWeek = costs[1] + mincostTickets(getNextDayToBuy(dayIndex, days, 7), days, costs);
int totalCostMonth = costs[2] + mincostTickets(getNextDayToBuy(dayIndex, days, 30), days, costs);
// Return the one with min totalCost
memo[dayIndex] = Math.min(totalCostMonth, Math.min(totalCostDay, totalCostWeek));
return memo[dayIndex];
}
private int getNextDayToBuy(int dayIndex, int[] days, int duration) {
int endDay = days[dayIndex] + duration - 1;
int newDayIndex = dayIndex;
while (newDayIndex < days.length && days[newDayIndex] <= endDay) {
newDayIndex++;
}
return newDayIndex;
}