Day 7 : 983. Minimum Cost For Tickets

You need to buy train passes to cover specific travel days in a year while spending the least amount of money. There are three types of passes:

1-day pass (covers only one day)

7-day pass (covers seven consecutive days)

30-day pass (covers thirty consecutive days)

Given an array of days and costs, return the minimum number of dollars you need to travel every day. 

Before we get started let's take a deep breath…This is f%$! hard but it’s worth doing if you want to pursue a career in tech.

It took me some good time to wrap my head around this problem, so let’s take it step by step!

• What are we asked? Find the minimum cost required to buy train passes that cover all the given travel days.

• If you purchase a multi-day pass, it covers all days within its validity period, so you don’t need to pay again for those days.

Now before we continue, there is an important realization you’ll make when doing this problem that is also applicable to real life. It will only be profitable to purchase a ticket that covers multiple days if its cost does not exceed the total cost of buying single-day passes for the same period.

So for each day that we are traveling we need to calculate the cost of buying:

• 1 Day Pass

• 7 Day Pass

• 30 Day Pass

and figuring out which is, cheaper 🤑 .

The keyword on identifying that it is a dynamic programming problem is “Minimum Cost”.

If you need a refresher on dynamic programming.

Let's look at an example with days = [1,4,6,7,8,20], costs = [2,7,15]  

This problem is tricky because we need to account for all travel days, therefore, we need to add all of the days to the DP array.

We initialize our dp array with:

vector<int> dp (days.back()+1, -1);

We set the dp array size to days.back() + 1, which includes our last travel day, making sure we account for all travel days while calculating the minimum cost.

To efficiently check whether a given day is a travel day, we store all travel days in a set, allowing O(1) lookup time when determining whether we need to buy a pass for a particular day.

set<int> travelDays(days.begin(), days.end()); 

Remember all DP problems follow a formula:

1.  Base Case: We know that on day 0, the cost is 0 since no travel has occurred:

dp[0] = 0; // No cost on day 0

2. Memoization: We'll use an array dp where dp[i] represents the minimum cost required to travel up to day i.

   • If i is not a travel day, dp[i] = dp[i - 1] (carry forward the previous day's cost).

3. Formula : Calculate the cost of the three options and find the cheapest.

int dayPass = dp[x-1]+costs[0]; 
int sevenDayPass = dp[max(0,x-7)]+costs[1]; 
int thirtyDayPass = dp[max(0, x-30)] + costs[2]; 
dp[x] = min({dayPass,sevenDayPass,thirtyDayPass});

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp (days.back()+1, -1); 
        dp[0]=0; 
        set<int> travelDays(days.begin(), days.end()); 
        for(int x=1; x<=days.back(); x++){
            if( travelDays.find(x)==travelDays.end()){
                dp[x] = dp[x-1]; 
                continue;
            }
            int dayPass = dp[x-1]+costs[0]; 
            int sevenDayPass = dp[max(0,x-7)]+costs[1]; 
            int thirtyDayPass = dp[max(0, x-30)] + costs[2]; 
            dp[x] = min({dayPass,sevenDayPass,thirtyDayPass});
        }
        return dp[dp.size()-1]; 
    }
};

Let me invoke you into my cult

Media worth seeing

1. Apply to YC AI Startup School

2.  How to Not Suck at Your Job 

3. How to start angel investing

4. How to write a newsletter and learn copywriting

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!