If you have any query feel free to chat us!
Happy Coding! Happy Learning!
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 arraycosts
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 arraydays
representing the travel days and an arraycosts
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), wheren
is the number of travel days. The space complexity is O(n) due to the dynamic programming arraydp
.
Comments: 2
SCIAKU Team please upload 1st video of TREE please please please, please
I bought this course, it worth it!
Hi i want to buy this course but you dont have master card payment method please let me know how i can buy it
Dear mk.info.work, Now we have all types of payment options. If you need to purchase just checkout our official website