Minimum Costs Using the Train Line

class Solution {
public:
    vector<long long> computeMinCosts(vector<int>& standard, vector<int>& premium, int upgradeFee) {
        int size = standard.size() + 1;
        
        long minStandard = 0;
        long minPremium = upgradeFee;
        
        vector<long long> result;
        for (int i = 1; i < size; i++) {
            long costStandard = standard[i - 1] + min(minStandard, minPremium);
            long costPremium = premium[i - 1] + min(minPremium, minStandard + upgradeFee);
            
            result.push_back(min(costStandard, costPremium));
            
            minStandard = costStandard;
            minPremium = costPremium;
        }
        
        return result; 
    }
};

In this solution, the objective is to determine the minimum costs of traveling using a train system that offers both standard and premium services, along with an option to upgrade from standard to premium. The code uses the C++ programming language.

The function computeMinCosts() in the Solution class takes three parameters:

• standard - a vector of integers representing the cost of traveling via standard class for each trip.
• premium - a vector of integers representing the cost of traveling via premium class for each trip.
• upgradeFee - an integer representing the cost to upgrade from standard to premium.

The function initializes two variables to track the minimum accumulated cost for each train line:

• minStandard - initially set to 0 to indicate no cost has been accumulated for standard travel yet.
• minPremium - starts off as the upgradeFee, representing the minimal initial cost of starting with premium class by upgrading from standard.

A result vector, result, is used to store the minimum cost for each segment of the journey.

The method iterates over each segment from 1 to the size of the standard and premium vectors. For each segment, the code computes:

• costStandard - the cost if travelling on standard class for this segment, taking the lower cost of either continuing in standard class or switching from premium to standard.
• costPremium - the cost if using premium class, accounting for both, continued travel in premium or a fresh upgrade from standard in this segment.

The minimum of costStandard and costPremium for the current segment is pushed into the result vector. It then updates minStandard and minPremium to the calculated costs for the current segment, ensuring that each segment's calculations are based on the optimal choices of all preceding segments.

Finally, the function returns the result vector containing the minimized costs for each segment of the journey. This implementation ensures that the traveler always spends the least amount possible, given the costs of each travel class and the upgrade fee.

class Solution {
    public long[] calculateMinimumCost(int[] standard, int[] express, int upgradeCost) {

        long previousStandard = 0;
        long previousExpress = upgradeCost;

        long[] result = new long[standard.length];
        for (int idx = 1; idx < standard.length + 1; idx++) {
            long costStandard = standard[idx - 1] + Math.min(previousStandard, previousExpress);
            long costExpress = express[idx - 1] + Math.min(upgradeCost + previousStandard, previousExpress);

            result[idx - 1] = Math.min(costStandard, costExpress);

            previousStandard = costStandard;
            previousExpress = costExpress;
        }

        return result;

    }
}

The provided Java solution determines the minimum cost of traveling through a train line using two potential routes: the standard line and the express line, with the option to upgrade from standard to express at a fixed cost. The method calculateMinimumCost accepts three parameters: arrays representing the cost of each station in the standard and express lines, and an integer representing the upgrade cost.

Follow these steps to understand the algorithm implemented in the Java class:

1. Initialize two long variables, previousStandard and previousExpress, where previousStandard starts at 0, and previousExpress starts with the initial cost of upgrading.

2. Create an array result to store the minimum cost to reach each station.

3. Use a loop to iterate through each train station, beginning from the first station. In each iteration:

   • Calculate the cost of reaching the current station via the standard line by adding the cost at the current station to the minimum of the cost of being at the previous station on the standard or express line.
   • Similarly, calculate the cost of reaching the current station via the express line. This cost is the sum of the express line cost at the current station and the lesser of being at the previous station on the standard line plus the upgrade cost, or the express line cost at the previous station.
   • Store the minimum of these two calculated costs in the result array.

4. Update previousStandard and previousExpress with the calculated costs for the current station to use in the next iteration.

5. Return the result array, which now contains the minimum cost to reach each station using either the standard or express line, selecting the optimal route at each step.

This approach ensures optimal utilization of both lines based on the costs and provides a dynamic solution to minimize overall travel expenses through recursive comparison and direct computation.