Minimum Cost For Tickets

Leetcode Problem:

• Minimum Cost For Tickets

Summary

• The problem is to find the minimum cost of traveling a list of days given the costs of 1-day, 7-day, and 30-day passes.

Approach

• Dynamic programming is used to solve this problem
• The idea is to create a dp array where dp[i] represents the minimum cost to reach day i
• The dp array is initialized with zeros and then filled up in a bottom-up manner
• For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
• Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day.

Complexity

• O(n) where n is the number of days.

Explanation

• The dynamic programming approach is used to solve this problem efficiently
• The dp array is filled up in a bottom-up manner, starting from day 1
• For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
• Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day
• This approach avoids the need to calculate the cost for each day multiple times, making it more efficient.

Solution Code:

class Solution {
public:
    int mincostTickets(vector& days, vector& costs) {
        int lastDay = days[days.size() - 1];
        vector dp(lastDay + 1, 0);
        
        int i = 0;
        for (int day = 1; day <= lastDay; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;
                dp[day] = min({dp[day - 1] + costs[0],
                               dp[max(0, day - 7)] + costs[1],
                               dp[max(0, day - 30)] + costs[2]});
            }
        }
     
        return dp[lastDay];
    }
};