Lecture 105:- Minimum Cost For Tickets

The Minimum Cost For Tickets problem is another classic dynamic programming problem. In this problem, you are given an array days representing days you plan to travel and an array costs representing the cost of each type of ticket (1-day, 7-day, and 30-day). You need to find the minimum cost to cover all the travel days.

Here's a Python function that implements the Minimum Cost For Tickets algorithm using dynamic programming:

pythonCopy code

def mincost_tickets(days, costs):    n = len(days)    durations = [1, 7, 30]    dp = [float('inf')] * (n + 1)    dp[0] = 0    for i in range(1, n + 1):        for j in range(len(durations)):            k = i - 1            while k >= 0 and days[i - 1] - days[k] < durations[j]:                k -= 1            dp[i] = min(dp[i], dp[k + 1] + costs[j])    return dp[n] # Test the function days = [1, 4, 6, 7, 8, 20] costs = [2, 7, 15] print(mincost_tickets(days, costs))  # Output: 11 (2 + 2 + 7)

In this code, the mincost_tickets() function takes an array days representing the travel days and an array costs representing the cost of 1-day, 7-day, and 30-day tickets.

The dynamic programming approach iteratively fills the dp array based on the minimum cost needed to cover the travel days up to each index. For each travel day, it considers the minimum cost for the previous travel day and the cost of a ticket with each duration (1-day, 7-day, and 30-day) that covers the current travel day.

The result is stored in dp[n], which represents the minimum cost to cover all the travel days. The time complexity of this solution is O(n), where n is the number of travel days. The space complexity is O(n) due to the dynamic programming array dp.