Solution For Minimum Cost For Tickets

Description:

You have to travel to N cities from city 1 to N. There are different costs for ticket purchases. You have to minimize the sum of the ticket costs to reach the destination.

Limited passes:

1-day ticket – costs 1 unit.
7-day ticket – costs 7 units.
30-day ticket – costs 30 units.

Note: The above prices are not interrelated. Each ticket is bought for the exact number of days. In that way, if you want to fly from day i to day j (j > i), you have to buy passes covering all the days between i and j.

Example:

Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11
Explanation:
The week pass is valid for days 1, 2, 3, 4, 5, 6, and 7.
The day pass is valid for everyday.
The month pass is valid for days 1 to 30 of every month.
The total price using this strategy is: 2 + 7 + 2 = 11.

Solution:

To address this issue, we can utilize dynamic programming. Before we begin programming, let’s think about the recursive formula for the issue.

dp[i] represents the minimum expense expected to fly from city 1 to city i. Then, we can reinforce the recursive formula.

case 1. When we don’t require a travel pass

If we don’t need a travel pass for city i, the recursive formula
dp[i] = dp[i – 1]

case 2. When we need to purchase a travel pass

If we need to purchase a travel pass for city i, there can be three forms of passes: the 1-day pass, the 7-day pass, and the 30-day pass. The issue requires us to locate the minimum of the three.

dp[i] = min(dp[i – 1] + costs[0], dp[max(0, i – 7)] + costs[1], dp[max(0, i – 30)] + costs[2])

Here, we set the max() limit so that we don’t transcend the range when we buy the pass earlier in the array than city i. The costs[] categories store the price of the day pass, week pass, and month pass, sequentially.

In summary, we have two scenarios. If we don’t require a travel pass for city i, take the previous optimal cost. If we need the pass, pick between the present cost and the pass cost plus the minimum optimized expense at 7 or 30 days before the present day.

We can extend the above formula to the whole array, resulting in O(N) possible answers. Fortunately, due to many overlapping sub-problems, we can use dynamic programming to save time.

Step by Step Implementation For Minimum Cost For Tickets

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length-1];
        int[] dp = new int[lastDay+1];
        // Base case: no travel
        dp[0] = 0;
        
        // Iterate over each day
        for (int i = 1; i <= lastDay; i++) {
            // If day i is not a travel day, then cost is same as day before
            if (!contains(days, i)) {
                dp[i] = dp[i-1];
            }
            // Otherwise, we need to find the minimum cost of the three options
            else {
                // Option 1: 1-day pass
                int cost1 = dp[i-1] + costs[0];
                // Option 2: 7-day pass
                int cost2 = (i >= 7) ? dp[i-7] + costs[1] : costs[1];
                // Option 3: 30-day pass
                int cost3 = (i >= 30) ? dp[i-30] + costs[2] : costs[2];
                // Take the minimum cost of the three options
                dp[i] = Math.min(cost1, Math.min(cost2, cost3));
            }
        }
        // Return the cost for the last day
        return dp[lastDay];
    }
    
    // Helper method to check if an array contains a given value
    private boolean contains(int[] arr, int val) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == val) {
                return true;
            }
        }
        return false;
    }
}

This problem can be solved using a dynamic programming approach. We can create an array dp where dp[i] represents the minimum cost of tickets for days i through i+1. Then, we can iterate through the array and update the cost for each day based on the cost of the previous days.

For example, if we have the following array:

dp = [2, 7, 15]

We can update the cost for day 2 as follows:

dp[2] = min(dp[2], dp[1] + 2)

This means that the minimum cost of tickets for days 2 through 3 is 2 + the cost of the previous day.

We can continue this process until we reach the end of the array. The final result will be the minimum cost of tickets for the entire period.

/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function(days, costs) {
    // create a dp array to store the minimum cost for each day
    let dp = new Array(days.length).fill(0);
    
    // iterate through days array
    for (let i = 0; i < days.length; i++) {
        // set current cost to be the cost of the 1 day ticket
        let currentCost = costs[0];
        
        // iterate through all previous days
        for (let j = i - 1; j >= 0; j--) {
            // if the 7 day ticket would be cheaper than the current cost AND 
            // the current day is within 7 days of the previous day
            if (costs[1] < currentCost && days[i] - days[j] < 8) {
                // update the current cost to be the cost of the 7 day ticket
                currentCost = costs[1];
            }
            
            // if the 30 day ticket would be cheaper than the current cost AND 
            // the current day is within 30 days of the previous day
            if (costs[2] < currentCost && days[i] - days[j] < 31) {
                // update the current cost to be the cost of the 30 day ticket
                currentCost = costs[2];
            }
        }
        
        // update the dp array at the current index to be the current cost plus the cost of the ticket at the previous index
        dp[i] = currentCost + (i > 0 ? dp[i - 1] : 0);
    }
    
    // return the last element in the dp array (this will be the minimum cost for all days)
    return dp[dp.length - 1];
};

There are a number of ways to approach this problem. One way would be to use a greedy algorithm, where you always choose the cheapest ticket option available. Another way would be to use a dynamic programming approach, where you calculate the minimum cost for each day in the range and choose the cheapest option at each step.

Here is one possible solution using a greedy algorithm:

/*

Given a list of days on which you must travel and the cost of each type of ticket, find the minimum cost to travel all days.

*/

#include 
#include 
#include 

using namespace std;

int main() {
    // vector of days on which travel is required
    vector days = {1, 4, 6, 7, 8, 20};
    
    // cost of each type of ticket
    int cost_one_day = 2;
    int cost_seven_days = 7;
    int cost_thirty_days = 25;
    
    // minimum cost to travel all days
    int min_cost = 0;
    
    // current day we are considering
    int i = 0;
    
    while (i < days.size()) {
        // if we can purchase a seven-day ticket that covers the current day, do so
        if (i + 6 < days.size() && days[i + 6] >= days[i]) {
            min_cost += cost_seven_days;
            i += 7;
        } 
        // if we can purchase a thirty-day ticket that covers the current day, do so
        else if (i + 29 < days.size() && days[i + 29] >= days[i]) {
            min_cost += cost_thirty_days;
            i += 30;
        } 
        // otherwise, purchase a one-day ticket
        else {
            min_cost += cost_one_day;
            i++;
        }
    }
    
    cout << min_cost << endl;
    
    return 0;
}

using System; 

public class Solution {
    public int MincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.Length - 1];
        int[] minCosts = new int[lastDay + 1];
        minCosts[0] = 0;
        int dayIndex = 0;
        for (int i = 1; i <= lastDay; ++i) {
            if (i != days[dayIndex]) {
                minCosts[i] = minCosts[i - 1];
            }
            else {
                int minCost = minCosts[i - 1] + costs[0];
                minCost = Math.Min(minCost, 
                    (i >= 7 ? minCosts[i - 7] : 0) + costs[1]);
                minCost = Math.Min(minCost, 
                    (i >= 30 ? minCosts[i - 30] : 0) + costs[2]);
                minCosts[i] = minCost;
                dayIndex++;
            }
        }
        return minCosts[lastDay];
    }
}