LeetCode 2361: Minimum Costs Using the Train Line Solution

Master LeetCode problem 2361 (Minimum Costs Using the Train Line), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2361. Minimum Costs Using the Train Line

Hard

Array Dynamic Programming

Problem Explanation

Explanation:

The problem asks us to find the minimum cost to get from the start station to the end station using the train line. We are given the costs of traveling between adjacent stations in both directions and the cost of skipping a station. The solution involves dynamic programming to compute the minimum cost at each station while considering whether to skip the current station or not.

We maintain two arrays to store the minimum cost of reaching each station. One array represents the minimum cost when we don't skip the current station, and the other represents the minimum cost when we skip the current station.
We start by initializing the costs for the start station. The cost of reaching the start station without skipping is 0, and the cost of skipping it is the skip cost.
We iterate through the stations from the second one to the end, updating the minimum costs for each station based on the previous stations.
At each station, we calculate the minimum cost of reaching it without skipping by taking the minimum of the previous station's cost without skipping and the cost of going from the previous station to the current station. We also calculate the minimum cost of reaching it by skipping by taking the minimum of the previous station's cost without skipping and the previous station's cost with skipping.
Finally, the minimum cost to reach the end station is the minimum of the cost of reaching the end station without skipping and the cost of skipping the end station.

Solution Code

class Solution {
    public int minCost(int[] costs, int skipCost) {
        int n = costs.length;
        int[] dpNoSkip = new int[n];
        int[] dpSkip = new int[n];
        
        dpNoSkip[0] = 0;
        dpSkip[0] = skipCost;
        
        for (int i = 1; i < n; i++) {
            dpNoSkip[i] = Math.min(dpNoSkip[i - 1] + costs[i - 1], dpSkip[i - 1]);
            dpSkip[i] = Math.min(dpNoSkip[i - 1], dpSkip[i - 1] + skipCost);
        }
        
        return Math.min(dpNoSkip[n - 1] + costs[n - 1], dpSkip[n - 1]);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2361 (Minimum Costs Using the Train Line)?

This page provides optimized solutions for LeetCode problem 2361 (Minimum Costs Using the Train Line) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2361 (Minimum Costs Using the Train Line)?

The time complexity for LeetCode 2361 (Minimum Costs Using the Train Line) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2361 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2361 in Java, C++, or Python.

Back to LeetCode Solutions