Minimum Cost of Tickets

Fastrail08

May 25th, 2025

153

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.26 KB | None | 0 0

raw download clone embed print report

//QUESTION
// https://leetcode.com/problems/minimum-cost-for-tickets/?envType=problem-list-v2&envId=9otti25c
#include <bits/stdc++.h>
using namespace std;
void getMinCostToTravel(int index, int currCost, int freeTravelUpto, int &minCost, vector<int> &days, vector<int> &cost){
//base case
if(index >= days.size()){
minCost = min(minCost, currCost);
return;
}
//level - each day
//options - each pass options tried on every level
// if the day is not covered in the pass brought on a previous day, buy a new one (with every option each to generate all the possibilites)
if(days[index] > freeTravelUpto){
for(int i = 0; i < cost.size(); i++){
int pass = i == 0 ? 1 : i == 1 ? 7 : 30;
getMinCostToTravel(index + 1, currCost + cost[i], days[index] + (pass - 1), minCost, days, cost);
}
}
// if the day is already covered by a pass brought on some previous day, don't buy,just move to next day
else{
getMinCostToTravel(index + 1, currCost, freeTravelUpto, minCost, days, cost);
}
}
int getMinCostToTravelMemo (int index, int freeTravelUpto, vector<int> &days, vector<int> &cost){
//base case
if(index >= days.size()){
return 0;
}
int minCost = INT_MAX;
if(days[index] > freeTravelUpto){
for(int i = 0; i < cost.size(); i++){
int pass = i == 0 ? 1 : i == 1 ? 7 : 30;
minCost = min(minCost, cost[i] + getMinCostToTravelMemo(index + 1, days[index] + (pass - 1), days, cost));
}
}
// if the day is already covered by a pass brought on some previous day, don't buy,just move to next day
else{
minCost = getMinCostToTravelMemo(index + 1, freeTravelUpto, days, cost);
}
return minCost;
}
int main() {
// your code goes here
int n;
cin >> n;
vector<int> days(n), cost(3);
for(int i = 0; i < n; i++){
cin >> days[i];
}
for(int i = 0; i < n; i++){
cin >> cost[i];
}
int freeTravelUpto = 0, minCost = INT_MAX;
// getMinCostToTravel(0, 0, freeTravelUpto, minCost, days, cost);
// cout << minCost << '\n';
cout << getMinCostToTravelMemo(0, freeTravelUpto, days, cost) << '\n';
}

Add Comment

Please, Sign In to add comment