Minimum Costs Using the Train Line

This problem involves finding the minimum cost to reach each stop from the starting stop (stop 0) using either a regular or express train route, with a cost associated with switching between routes. We can solve this efficiently using dynamic programming.

Approach: Dynamic Programming

We'll use dynamic programming to track the minimum cost to reach each stop using two arrays:

• f[i]: Minimum cost to reach stop i using the regular route.
• g[i]: Minimum cost to reach stop i using the express route.

The base cases are:

• f[0] = 0 (starting at stop 0 on the regular route)
• g[0] = Infinity (we start on the regular route, so the initial cost for the express route is infinitely high)

The recurrence relations are:

• f[i] = min(f[i-1] + regular[i-1], g[i-1] + regular[i-1]) To reach stop i via the regular route, we can either come from the previous stop on the regular route, or switch from the express route at the previous stop.

• g[i] = min(f[i-1] + expressCost + express[i-1], g[i-1] + express[i-1]) To reach stop i via the express route, we can either switch from the regular route at the previous stop (incurring the expressCost), or continue from the express route.

Finally, the minimum cost to reach stop i is min(f[i], g[i]).

Time and Space Complexity

• Time Complexity: O(n), where n is the number of stops. We iterate through the stops once.
• Space Complexity: O(n) in the initial solution (using arrays f and g). We can optimize this to O(1) by only storing the minimum costs for the previous stop.

Code Implementation (Optimized Space Complexity)

The code examples below demonstrate the optimized solution with O(1) space complexity.

Python:

def minimumCosts(regular, express, expressCost):
    n = len(regular)
    f, g = 0, float('inf')  # Initialize f and g
    costs = []
    for i in range(n):
        new_f = min(f + regular[i], g + regular[i])
        new_g = min(f + expressCost + express[i], g + express[i])
        costs.append(min(new_f, new_g))
        f, g = new_f, new_g  # Update f and g for the next iteration
    return costs
 

Java:

class Solution {
    public long[] minimumCosts(int[] regular, int[] express, int expressCost) {
        int n = regular.length;
        long f = 0;
        long g = Long.MAX_VALUE;
        long[] costs = new long[n];
        for (int i = 0; i < n; i++) {
            long newF = Math.min(f + regular[i], g + regular[i]);
            long newG = Math.min(f + expressCost + express[i], g + express[i]);
            costs[i] = Math.min(newF, newG);
            f = newF;
            g = newG;
        }
        return costs;
    }
}

C++:

vector<long long> minimumCosts(vector<int>& regular, vector<int>& express, int expressCost) {
    int n = regular.size();
    long long f = 0;
    long long g = LLONG_MAX;
    vector<long long> costs(n);
    for (int i = 0; i < n; ++i) {
        long long new_f = min(f + (long long)regular[i], g + (long long)regular[i]);
        long long new_g = min(f + (long long)expressCost + (long long)express[i], g + (long long)express[i]);
        costs[i] = min(new_f, new_g);
        f = new_f;
        g = new_g;
    }
    return costs;
}

JavaScript:

const minimumCosts = (regular, express, expressCost) => {
    const n = regular.length;
    let f = 0;
    let g = Infinity;
    const costs = [];
    for (let i = 0; i < n; i++) {
        const newF = Math.min(f + regular[i], g + regular[i]);
        const newG = Math.min(f + expressCost + express[i], g + express[i]);
        costs.push(Math.min(newF, newG));
        f = newF;
        g = newG;
    }
    return costs;
};

These optimized solutions achieve the same result with improved space efficiency. Remember to handle potential integer overflow issues, especially with larger input values, as shown in the C++ example.